The Computer Journal Advance Access published online on July 30, 2007
The Computer Journal, doi:10.1093/comjnl/bxm049
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Fixed-Parameter Algorithms in Phylogenetics
1 Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Germany
2 Institut für Theoretische Informatik, Universität zu Lübeck, Germany
* Corresponding author: tantau{at}tcs.uni-luebeck.de
Received 15 March 2006; revised 28 July 2006
We survey the use of fixed-parameter algorithms in the field of phylogenetics, which is the study of evolutionary relationships. The central problem in phylogenetics is the reconstruction of the evolutionary history of biological species, but its methods also apply to linguistics, philology or architecture. A basic computational problem is the reconstruction of a likely phylogeny (genealogical tree) for a set of species based on observed differences in the phenotype like color or form of limbs, based on differences in the genotype like mutated nucleotide positions in the DNA sequence, or based on given partial phylogenies. Ideally, one would like to construct socalled perfect phylogenies, which arise from a very simple 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 has applications in seemingly unrelated areas such as genomic sequencing and finding and understanding genes. The numerous computational problems arising in phylogenetics often are NP-complete, but for many natural parametrizations they can be solved using fixed-parameter algorithms.
Key Words: bioinformatics • phylogenetics algorithms • parameterized algorithms