Fixed-Parameter Algorithms in Phylogenetics

Jens Gramm, Arfst Nickelsen, Till Tantau


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.
TitelMethods in Molecular Biology : Bioinformatics: Volume I: Data, Sequence Analysis and Evolution
Herausgeber (Verlag)Springer Berlin Heidelberg
PublikationsstatusVeröffentlicht - 2008