Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree
Algorithms for the Majority Rule (+) Consensus Tree and the Frequency Difference Consensus Tree
复制标题
多数规则（ ）共识树和频差共识树的算法
DOI：
10.1109/tcbb.2016.2609923
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
and W.-K. Sung
中科院分区：
文献类型：
--
作者：
J. Jansson;R. Rajaby;C. Shen;and W.-K. Sung
本文提出了两个新的确定性算法构造共识树。给定k个具有相同叶子标签集和n个叶子的系统发生树的输入，第一个算法在O（kn）时间内构建多数规则（+）一致性树，这是最优的，因为输入大小为Ω（kn），第二个算法在min{O（kn 2），O（kn（k + log 2n））}时间内构建频率差一致性树。
This article presents two new deterministic algorithms for constructing consensus trees. Given an input of k phylogenetic trees with identical leaf label sets and n leaves each, the first algorithm constructs the majority rule (+) consensus tree in O(kn) time, which is optimal since the input size is Ω (kn), and the second one constructs the frequency difference consensus tree in min{O(kn2), O(kn(k + log2n))} time.