...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithms for Molecular Biology >Towards a practical O(nlogn) phylogeny algorithm
【24h】

Towards a practical O(nlogn) phylogeny algorithm

机译：面向实用的O（nlogn）系统进化算法

获取原文
   

获取外文期刊封面封底 >>

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

摘要

Recently, we have identified a randomized quartet phylogeny algorithm that has O(nlogn) runtime with high probability, which is asymptotically optimal. 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 Θ(n3) runtime in existing implementations. Our results suggest a new direction for quartet-based phylogenetic reconstruction that may yield striking speed improvements at minimal accuracy cost. An early prototype implementation of our software is available at http://www.cs.uwaterloo.ca/jmtruszk/qtree.tar.gz webcite .
机译：最近，我们确定了一个随机的四方系统发生算法，该算法具有很高的O（nlogn）运行时间，这是渐近最优的。当四重奏错误是独立的并且以已知概率发生时，并且当算法在O（loglogn）分类群上使用指导树的概率很高时，我们的算法返回正确的系统发育的可能性很高。实际上，这些假设都不是正确的：四元组错误与正相关并且以未知的概率发生，并且指导树通常容易出错。在这里，我们将我们的工作从纯粹的理论出发。我们提出了各种各样的扩展，这些扩展虽然仅使算法减慢了一个恒定因子，但使其性能几乎可以与Neighbor Joining相比，后者在现有实现中需要Θ（n 3 ）运行时。我们的结果为基于四重态的系统发育重建提出了新的方向，该方向可能会以最低的精度成本显着提高速度。可在http://www.cs.uwaterloo.ca/jmtruszk/qtree.tar.gz网站上找到我们软件的早期原型实现。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号