• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Algorithms in bioinformatics >Towards a Practical O(n log n) Phylogeny Algorithm
【24h】

Towards a Practical O(n log n) Phylogeny Algorithm

机译：面向实用的O（n log n）系统发育算法

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

摘要

Recently, we have identified a quartet phylogeny algorithm with O(n log n) expected runtime, which is asymptotically optimal. Regardless of the true topology, our algorithm has high probability of returning the correct phylogeny when quartet errors are independent and occur with known probability, and when the algorithm uses a guide tree on O(log log n) taxa that is correct with high probability. In practice, none of these assumptions is correct: quartet errors are positively correlated and occur with unknown probability, and the guide tree is often error prone. Here, we bring our work out of the purely theoretical setting. We present a variety of extensions which, while only slowing the algorithm down by a constant factor, make its performance nearly comparable to that of neighbour-joining, which requires O(n~3) runtime. Our results suggest a new direction for quartet-based phylogenetic reconstruction that may yield striking speed improvements at minimal accuracy cost.
机译：最近，我们确定了具有O（n log n）预期运行时间的四重系统进化算法，该算法是渐近最优的。无论真正的拓扑如何，当四元组错误是独立的并且以已知概率发生时，并且当算法对O（log log n）分类群使用导引树的概率都很高时，我们的算法很有可能返回正确的系统发育。实际上，这些假设都不是正确的：四元组错误与正相关并且以未知的概率发生，并且指导树经常容易出错。在这里，我们将我们的工作从纯粹的理论出发。我们提出了各种各样的扩展，这些扩展虽然仅使算法减慢了一个恒定因子，但使其性能几乎与邻居连接的性能相当，后者需要O（n〜3）运行时。我们的结果为基于四方的系统发育重建提出了一个新的方向，该方向可能会以最低的精度成本显着提高速度。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号