Fixed-Parameter Algorithms in Phylogenetics

Jens Gramm, Arfst Nickelsen, Till Tantau

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.
Original languageEnglish
Title of host publicationMethods in Molecular Biology : Bioinformatics: Volume I: Data, Sequence Analysis and Evolution
Volume452
PublisherSpringer Berlin Heidelberg
Publication date2008
Pages507-535
Publication statusPublished - 2008

Cite this