*Jens Gramm, Arfst Nickelsen, Till Tantau*:

**Fixed-Parameter Algorithms in Phylogenetics.**

In *Bioinformatics: Volume I: Data, Sequence Analysis and Evolution, *Volume 452 of *Methods in Molecular Biology, *pp. 507-535.
Springer,
2008.

Show 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.