首页> 外文期刊>Computational Biology and Bioinformatics, IEEE/ACM Transactions on >An Efficient Algorithm for Approximating Geodesic Distances in Tree Space
【24h】

An Efficient Algorithm for Approximating Geodesic Distances in Tree Space

机译:树空间中测地距离的一种高效算法

获取原文
获取原文并翻译 | 示例

摘要

The increasing use of phylogeny in biological studies is limited by the need to make available more efficient tools for computing distances between trees. The geodesic tree distance—introduced by Billera, Holmes, and Vogtmann—combines both the tree topology and edge lengths into a single metric. Despite the conceptual simplicity of the geodesic tree distance, algorithms to compute it don't scale well to large, real-world phylogenetic trees composed of hundred or even thousand leaves. In this paper, we propose the geodesic distance as an effective tool for exploring the likelihood profile in the space of phylogenetic trees, and we give a cubic time algorithm, GeoHeuristic, in order to compute an approximation of the distance. We compare it with the GTP algorithm, which calculates the exact distance, and the cone path length, which is another approximation, showing that GeoHeuristic achieves a quite good trade-off between accuracy (relative error always lower than 0.0001) and efficiency. We also prove the equivalence among GeoHeuristic, cone path, and Robinson-Foulds distances when assuming branch lengths equal to unity and we show empirically that, under this restriction, these distances are almost always equal to the actual geodesic.
机译:由于需要提供更有效的工具来计算树木之间的距离,因此限制了系统生物学在生物学研究中的越来越多的使用。由Billera,Holmes和Vogtmann引入的测地线树距离将树形拓扑和边长合并为一个度量。尽管从概念上讲,测地线树距离很简单,但是计算它的算法无法很好地缩放到由上百个甚至上千个叶子组成的大型现实系统树。在本文中,我们提出了测地线距离作为探索系统树树木空间中的似然分布的有效工具,并给出了三​​次时间算法GeoHeuristic,以计算距离的近似值。我们将其与GTP算法(后者计算出精确的距离)和圆锥路径长度(这是另一个近似值)进行比较,表明GeoHeuristic在精度(相对误差始终低于0.0001)和效率之间取得了很好的折衷。当假设分支长度等于1时,我们还证明了GeoHeuristic距离,圆锥路径和Robinson-Foulds距离之间的等效性,并根据经验证明,在这种限制下,这些距离几乎总是等于实际测地线。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号