OPTIMAL-ALGORITHMS FOR COMPARING TREES WITH LABELED LEAVES
OPTIMAL-ALGORITHMS FOR COMPARING TREES WITH LABELED LEAVES
复制标题
DOI：
10.1007/bf01908061
复制
发表时间：
1985-01-01
影响因子：
2
通讯作者：
DAY, WHE
中科院分区：
文献类型：
--
作者：
DAY, WHE
令 Rn 表示具有 n 个叶子的有根树的集合，其中叶子由 { 1, ... 中的整数标记。 。 。 , n};在内部顶点中，只有根的度数可以为 2。与此类树中的每个内部顶点 v 相关联的是以 v 为根的子树中的叶标签的子集或簇。簇 {1,…. 。 。 , n} 被称为微不足道的。聚类用于定量测量树之间的相似性、相异性和一致性。对于 Rn 中的任何 k 棵树，严格共识树 C(T1,...,Tk) 是 Rn 中恰好包含 k 棵树中每一棵树所共有的簇的树。 Rn 中树 T1 和 T2 之间的相似性通过 T1 和 T2 中非平凡簇的数量 S(T1, T2) 来衡量；相异性，由 T1 或 T2 中簇的数量 D(T1, T2) 决定，但两者都不同。已知算法在 O(kn2) 时间内计算 C(T1,...,Tk)，并在 O(N2) 时间内计算 S(T1,T2) 和 D(T1,T2)。提出了 Rn 中任何树 T 的簇的特殊表示，允许在恒定时间内测试给定簇是否存在于 T 中。描述了利用该表示在 O(kn) 时间内计算 C(T1,...,Tk) 以及在 O(n) 时间内计算 S(T1, T2) 和 D(T1, T2) 的算法。这些算法在技术意义上是最优的。它们使得能够在 O(n) 时间内计算出两棵[系统发育]树之间众所周知的共识索引。所有这些结果也适用于涉及带有标记叶子的无根树的类似问题。
Let Rn denote the set of rooted trees with n leaves in which the leaves are labeled by the integers in { 1, . . . , n}; and among interior vertices only the root may have degree 2. Associated with each interior vertex v in such a tree is the subset, or cluster, of leaf labels in the subtree rooted at v. Cluster {1, . . . , n} is called trivial. Clusters are used in quantitative measures of similarity, dissimilarity and consensus among trees. For any k trees in Rn, the strict consensus tree C(T1, . . . , Tk) is that tree in Rn containing exactly those clusters common to every one of the k trees. Similarity between trees T1 and T2 in Rn is measured by the number S(T1, T2) of nontrivial clusters in both T1 and T2; dissimilarity, by the number D(T1, T2) of clusters in T1 or T2 but not in both. Algorithms are known to compute C(T1, . . . , Tk) in O(kn2) time, and S(T1, T2) and D(T1, T2) in O(N2) time. A special representation of the clusters of any tree T in Rn, is proposed that permits testing in constant time whether a given cluster exists in T. Algorithms are described that exploit this representation to compute C(T1, . . . , Tk) in O(kn) time, and S(T1, T2) and D(T1, T2) in O(n) time. These algorithms are optimal in a technical sense. They enable well-known indices of consensus between 2 [phylogenetic] trees to be computed in O(n) time. All these results apply as well to comparable problems involving unrooted trees with labeled leaves.