• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic
【24h】

Parsimony Score of Phylogenetic Networks: Hardness Results and a Linear-Time Heuristic

机译：系统发育网络的简约分数：硬度结果和线性时间启发式

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 ldquoforbidden cycles,rdquo and provide detailed hardness and hardness of approximation proofs for the "smallrdquo 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.
机译：系统发育是生物群的进化历史，在代表生物实体之间的相互关系中起着重要作用。已经提出了许多重建和研究这种系统发育的方法，几乎​​所有方法都假定给定物种集的基础历史可以用二叉树表示。尽管可以通过这种方式有效地对许多生物过程进行建模和总结，但是其他生物过程则不能：重组，杂种形成和水平基因转移产生关系网络，而不是关系树。在以前的工作中，我们制定了用于重构和评估系统进化网络的最大简约（MP）标准，并在生物学和合成数据集上证明了其质量。在本文中，我们为系统发育网络的MP准则提供了进一步的理论结果以及非常快速的启发式算法。特别是，我们根据“禁止循环”提供了系统的新的系统组合，并提供了“小MP问题”的详细硬度和近似证明的硬度。我们在时间和准确性方面都展示了我们的启发式方法的性能。最后，我们解释了我们的模型与Nguyen等人提出的类似模型之间的差异，并描述了这种差异对硬度和近似结果的影响。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号