Improved Algorithms for Constructing Consensus Trees
Improved Algorithms for Constructing Consensus Trees
复制标题
DOI：
10.1145/2925985
复制
发表时间：
2016-09-01
影响因子：
2.5
通讯作者：
Sung, Wing-Kin
中科院分区：
文献类型：
--
作者：
Jansson, Jesper;Shen, Chuanqi;Sung, Wing-Kin
共识树是一个单一的系统发生树，它总结了一组给定的冲突系统发生树中的分支结构。在文献中已经提出了许多不同类型的共识树，其中三种最知名和最广泛使用的是多数规则共识树，松散共识树和贪婪共识树。本文提出了新的确定性算法，用于构建它们，比以前已知的所有算法都要快。给定k个系统发育树，每个树有n个叶子，并且具有相同的叶子标签集，我们的算法运行在O（nk）时间（多数规则共识树），O（nk）时间（松散共识树）和O（n2k）时间（贪婪共识树）。我们的算法的多数规则的共识和松散的共识树是最佳的，因为输入大小是欧米茄（nk）。实验结果表明，该算法具有较好的实用性和快速性.
A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most well-known and widely used ones are the majority rule consensus tree, the loose consensus tree, and the greedy consensus tree. This article presents new deterministic algorithms for constructing them that are faster than all the previously known ones. Given k phylogenetic trees with n leaves each and with identical leaf label sets, our algorithms run in O(nk) time (majority rule consensus tree), O(nk) time (loose consensus tree), and O(n2k) time (greedy consensus tree). Our algorithms for the majority rule consensus and the loose consensus trees are optimal since the input size is Omega(nk). Experimental results show that the algorithms are fast in practice.