Contents of this article

Useful Tools
24. Fixed-Parameter Algorithms in Phylogenetics
Abstract
This chapter surveys 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, differences in the genotype, or 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.
Affiliation(s): (3) Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Tübingen, Germany
(4) Institut für Theoretische Informatik, Universität zu Lübeck, Lübeck, Germany
Series: Methods in Molecular Biology  |  Volume: 452  |  Pub. Date: May-01-2008  |  Page Range: 507-535  |  DOI: 10.1007/978-1-60327-159-2_24
Subject:  Bioinformatics
Comments (Loading...)
Loading...