Efficient parsimony-based methods for phylogenetic network reconstruction
Efficient parsimony-based methods for phylogenetic network reconstruction
复制标题
DOI：
10.1093/bioinformatics/btl313
复制
发表时间：
2007-01-15
期刊：
影响因子：
5.8
通讯作者：
Tuller, Tamir
中科院分区：
文献类型：
--
作者：
Jin, Guohua;Nakhleh, Luay;Tuller, Tamir
动机：系统发育--生物群体的进化历史--在代表生物实体之间的关系方面发挥着重要作用。虽然许多生物过程可以有效地建模为树状关系，但其他生物过程，如杂交物种形成和水平基因转移（HGT），会导致关系的网络，而不是树。杂交物种形成是植物、鱼类和其他物种的重要进化机制。HGT在细菌基因组多样化中起着重要作用，并且是细菌对抗生素产生耐药性的重要机制。最大简约性是系统发生树推断中最常用的准则之一。粗略地说，基于这个标准的推理寻找最小化进化量的树。在1990年，Jotun Hein提出使用这个标准来推断重组序列的进化。小型合成数据集的初步结果。Nakhleh等人（2005）证明了该标准在系统发育网络重建中的应用，特别是HGT检测。然而，作者使用的朴素算法不适用于大型数据集，由于其苛刻的计算要求。此外，没有严格的理论分析计算的标准，也没有测试生物data.Results：在目前的工作中，我们证明了得分的简约性的系统发育网络的问题是NP-难的，并提供了一个改进的固定参数听话algorithmforit. Further，我们设计了有效的基于简约重建的系统发育网络的算法。我们测试我们的方法在合成和生物数据（细菌中的rbcL基因），并获得非常有前途的结果。
Motivation: Phylogenies-the evolutionary histories of groups of organisms-play a major role in representing relationships among biological entities. Although many biological processes can be effectively modeled as tree-like relationships, others, such as hybrid speciation and horizontal gene transfer (HGT), result in networks, rather than trees, of relationships. Hybrid speciation is a significant evolutionary mechanism in plants, fish and other groups of species. HGT plays a major role in bacterial genome diversification and is a significant mechanism by which bacteria develop resistance to antibiotics. Maximum parsimony is one of the most commonly used criteria for phylogenetic tree inference. Roughly speaking, inference based on this criterion seeks the tree that minimizes the amount of evolution. In 1990, Jotun Hein proposed using this criterion for inferring the evolution of sequences subject to recombination. Preliminary results on small synthetic datasets. Nakhleh et al. (2005) demonstrated the criterion's application to phylogenetic network reconstruction in general and HGT detection in particular. However, the naive algorithms used by the authors are inapplicable to large datasets due to their demanding computational requirements. Further, no rigorous theoretical analysis of computing the criterion was given, nor was it tested on biological data.Results: In the present work we prove that the problem of scoring the parsimony of a phylogenetic network is NP-hard and provide an improved fixed parameter tractable algorithm for it. Further, we devise efficient heuristics for parsimony-based reconstruction of phylogenetic networks. We test our methods on both synthetic and biological data (rbcL gene in bacteria) and obtain very promising results.