Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic
Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic
复制标题
DOI：
10.1109/tcbb.2008.119
复制
发表时间：
2009-07-01
影响因子：
4.5
通讯作者：
Tuller, Tamir
中科院分区：
文献类型：
--
作者：
Jin, Guohua;Nakhleh, Luay;Tuller, Tamir
系统发育学--有机体群体的进化史--在描述生物实体之间的相互关系方面发挥着重要作用。已经提出了许多方法来重建和研究这样的系统发育，几乎所有的方法都假设一组给定物种的潜在历史可以用二叉树来表示。虽然许多生物过程可以用这种方式有效地建模和总结，但其他生物过程却不能：重组、杂交物种形成和水平基因转移导致关系网络而不是关系树。在以前的工作中，我们制定了一个最大简约(MP)标准来重建和评估系统发育网络，并在生物和合成数据集上证明了它的质量。本文给出了系统发育网络MP判据的进一步理论结果和一个非常快速的启发式算法。特别地，我们用“禁止环”的形式给出了系统发育网络的一种新的组合定义，并对“小”MP问题给出了详细的近似证明和困难证明。我们在生物和合成数据集上展示了我们的启发式算法在时间和准确性方面的性能。最后，我们解释了我们的模型与Nguyen等人提出的类似模型之间的差异，并描述了这种差异对硬度和近似结果的影响。
Phylogenies-the evolutionary histories of groups of organisms-play a major role in representing the interrelationships among biological entities. Many methods for reconstructing and studying such phylogenies have been proposed, almost all of which assume that the underlying history of a given set of species can be represented by a binary tree. Although many biological processes can be effectively modeled and summarized in this fashion, others cannot: recombination, hybrid speciation, and horizontal gene transfer result in networks of relationships rather than trees of relationships. In previous works, we formulated a maximum parsimony (MP) criterion for reconstructing and evaluating phylogenetic networks, and demonstrated its quality on biological as well as synthetic data sets. In this paper, we provide further theoretical results as well as a very fast heuristic algorithm for the MP criterion of phylogenetic networks. In particular, we provide a novel combinatorial definition of phylogenetic networks in terms of "forbidden cycles," and provide detailed hardness and hardness of approximation proofs for the "small" MP problem. We demonstrate the performance of our heuristic in terms of time and accuracy on both biological and synthetic data sets. Finally, we explain the difference between our model and a similar one formulated by Nguyen et al., and describe the implications of this difference on the hardness and approximation results.