On distances between phylogenetic trees
On distances between phylogenetic trees
复制标题
DOI：
--
复制
发表时间：
1997-01
影响因子：
4.1
通讯作者：
Bhaskar DasGupta;Xin He;Tao Jiang;Ming Li;J. Tromp;Louxin Zhang
中科院分区：
文献类型：
--
作者：
Bhaskar DasGupta;Xin He;Tao Jiang;Ming Li;J. Tromp;Louxin Zhang
在分子进化研究中，同一物种的不同系统发育树通常是通过使用不同的最优性标准或从不同的基因产生的。因此，比较这些树以找到它们的相似性和不同性，即距离，是计算分子生物学中的一个重要问题。最近邻交换距离和子树传输距离是两个主要的距离度量，由于不同的原因已经被提出并被广泛研究。尽管它们有许多吸引人的方面，如简单性和对树拓扑的敏感性，但计算这些距离仍然非常具有挑战性。本文研究了计算nni距离的复杂性和有效的近似算法，以及子树转移距离的自然扩展，称为线性代价子树转移距离。线性成本子树转移模型比子树转移模型更符合逻辑，并且在一定条件下与nni模型一致。下面的结果已经获得了作为我们的项目的一部分，建立一个全面的软件包，用于计算两个基因之间的距离。(1)计算nni距离是NP完全的。这解决了一个25年前的悬而未决的问题，例如，在P {ne} NP的复杂性理论假设下。我们还回答了一个关于未标记树之间的nni距离的openmore问题，其中出现了错误的证明。给出了一个计算时间为O（n{sup 2} logn + n {circ} 2{sup O（d）}）的最优nni序列的算法，其中nni距离不超过d. (2)生物学应用要求我们将nni和线性代价子树转移模型扩展到加权进化，其中边权重表示沿沿着每条边的进化长度。我们提出了一个对数比率近似算法nni和线性成本子树转移的比率2近似算法，加权树。«少
Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria or from different genes in the study of molecular evolution. Comparing these trees to find their similarities and dissimilarities, i.e. distance, is thus an important issue in computational molecular biology. The nearest neighbor interchange distance and the subtree-transfer distance are two major distance metrics that have been proposed and extensively studied for different reasons. Despite their many appealing aspects such as simplicity and sensitivity to tree topologies, computing these distances has remained very challenging. This article studies the complexity and efficient approximation algorithms for computing the nni distance and a natural extension of the subtree-transfer distance, called the linear-cost subtree-transfer distance. The linear-cost subtree-transfer model is more logical than the subtree-transfer model and in fact coincides with the nni model under certain conditions. The following results have been obtained as part of our project of building a comprehensive software package for computing distances between phylogenies. (1) Computing the nni distance is NP-complete. This solves a 25 year old open question appearing again and again in, for example, under the complexity-theoretic assumption of P {ne} NP. We also answer an openmore » question regarding the nni distance between unlabeled trees for which an erroneous proof appeared in. We give an algorithm to compute the optimal nni sequence in time O(n{sup 2} logn + n {circ} 2{sup O(d)}), where the nni distance is at most d. (2) Biological applications require us to extend the nni and linear-cost subtree-transfer models to weighted phylogenies, where edge weights indicate the length of evolution along each edge. We present a logarithmic ratio approximation algorithm for nni and a ratio 2 approximation algorithm for linear-cost subtree-transfer, on weighted trees.« less