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

Towards a Practical O(n log n) Phylogeny Algorithm

机译：朝向实际O（n log n）系统发育算法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Abstract. 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(loglogn) 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(n3) 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（loglogn）的引导树上以高概率来说是正确的。在实践中，这些假设都不是正确的：四重奏错误是肯定相关的并且具有未知概率，并且导向树通常容易出错。在这里，我们将我们的工作带出纯粹的理论环境。我们介绍了各种扩展，同时仅通过恒定因素减慢算法，其性能与邻接的性能几乎相当，这需要O（n3）运行时。我们的结果表明了基于四重奏的系统发育重建的新方向，可以以最小的精度成本产生引人注目的速度。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号