On the linear-cost subtree-transfer distance between phylogenetic trees
On the linear-cost subtree-transfer distance between phylogenetic trees
复制标题
DOI：
10.1007/pl00008273
复制
发表时间：
1999-10-01
期刊：
影响因子：
1.1
通讯作者：
Tromp, J
中科院分区：
文献类型：
--
作者：
DasGupta, B;He, X;Tromp, J
在分子进化研究中，同一物种群的不同系统发育树通常是由使用不同最优标准的程序[16]或由不同的基因[12]产生的。因此，比较这些树来发现它们的相似性和差异性（即距离）是计算分子生物学中的一个重要问题。包括最近邻交换（nni）距离和子树传输距离在内的几个距离度量已经被提出并在文献中进行了广泛的研究。本文考虑了子树传递距离的一种自然扩展，称为线性代价子树传递距离，并研究了该距离的复杂度和有效逼近算法，以及它与nni距离的关系。在某些应用中，线性代价子树转移模型似乎比（单位代价）子树转移模型更适用。以下是我们的结果列表：线性代价子树传递距离实际上与未加权系统发育上的nni距离相同。在0 (n)次系统发育之间，有一种计算最优线性代价子树转移序列的算法。2(O(d)))时间，其中d表示线性代价子树传递距离。当d很小时，这种算法是有用的。计算两个加权系统发育树之间的线性代价子树传递距离是np困难的，前提是我们允许树的多个叶子共享相同的标签（即，树不一定是唯一标记的）。对于计算性能比为2的加权系统发育之间的线性代价子树传递距离，有一种有效的近似算法。
Different phylogenetic trees for the same group of species are often produced either by procedures that use diverse optimality criteria [16] or from different genes [12] 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. Several distance metrics including the nearest neighbor interchange (nni) distance and the subtree-transfer distance have been proposed and extensively studied in the literature. This article considers a natural extension of the subtree-transfer distance, called the linear-cost subtree-transfer distance, and studies the complexity and efficient approximation algorithms for this distance as well as its relationship to the nni distance. The linear-cost subtree-transfer model seems more suitable than the (unit-cost) subtree-transfer model in some applications. The following is a list of our results:1. The linear-cost subtree-transfer distance is in fact identical to the nni distance on unweighted phylogenies.2. There is an algorithm to compute an optimal linear-cost subtree-transfer sequence between unweighted phylogenies in O (n . 2(O(d))) time, where d denotes the linear-cost subtree-transfer distance. Such an algorithm is useful when d is small.3. Computing the linear-cost subtree-transfer distance between two weighted phylogenetic trees is NP-hard, provided we allow multiple leaves of a tree to share the same label (i.e., the trees are not necessarily uniquely labeled).4. There is an efficient approximation algorithm for computing the linear-cost subtree-transfer distance between weighted phylogenies with performance ratio 2.