Gramm Jens, Nickelsen Arfst, Tantau Till
Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Tübingen, Germany.
Methods Mol Biol. 2008;452:507-35. doi: 10.1007/978-1-60327-159-2_24.
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.
本章概述了固定参数算法在系统发育学中的应用。该领域的一个核心计算问题是，根据观察到的表型差异、基因型差异或给定的部分系统发育关系，为一组物种构建一个可能的系统发育树（族谱树）。理想情况下，人们希望构建所谓的完美系统发育树，它源自一个基本的进化模型，但在实际中，人们常常不得不满足于那些“与完美的距离”尽可能小的系统发育树。系统发育树的计算在诸如基因组测序以及发现和理解基因等看似不相关的领域也有应用。系统发育学中出现的众多计算问题通常是NP完全问题，但对于许多自然参数化情况，它们可以使用固定参数算法来解决。
