Projects per year
Abstract
We survey the use of fixed-parameter algorithms in
phylogenetics. A central computational problem in
this field is the construction of a likely phylogeny
(genealogical tree) for a set of species based on
observed differences in the phenotype, on
differences in the genotype, or on given partial
phylogenies. Ideally, one would like to construct
so-called perfect phylogenies, which arise from an
elementary evolutionary model, but in practice one
must often be content with phylogenies whose
"distance from perfection" is as small as
possible. The computation of phylogenies also has
applications in seemingly unrelated areas such as
genomic sequencing and finding and understanding
genes. The numerous computational problems arising
in phylogenetics are often NP-complete, but for many
natural parametrizations they can be solved using
fixed-parameter algorithms.
phylogenetics. A central computational problem in
this field is the construction of a likely phylogeny
(genealogical tree) for a set of species based on
observed differences in the phenotype, on
differences in the genotype, or on given partial
phylogenies. Ideally, one would like to construct
so-called perfect phylogenies, which arise from an
elementary evolutionary model, but in practice one
must often be content with phylogenies whose
"distance from perfection" is as small as
possible. The computation of phylogenies also has
applications in seemingly unrelated areas such as
genomic sequencing and finding and understanding
genes. The numerous computational problems arising
in phylogenetics are often NP-complete, but for many
natural parametrizations they can be solved using
fixed-parameter algorithms.
Original language | English |
---|---|
Title of host publication | Methods in Molecular Biology : Bioinformatics: Volume I: Data, Sequence Analysis and Evolution |
Volume | 452 |
Publisher | Springer Berlin Heidelberg |
Publication date | 2008 |
Pages | 507-535 |
Publication status | Published - 2008 |
Projects
- 1 Finished
-
Complexity of haplotyping problems
Tantau, T., Schnoor, I., Elberfeld, M., Kuczewski, J. & Pohlmann, J.
01.01.05 → 31.12.10
Project: DFG Projects › DFG Individual Projects