A consensus tree is a phylogenetic tree that captures the similarity between a set of conflicting phylogenetic trees. The problem of computing a consensus tree is a major step in phylogenetic tree reconstruction. It is also central for predicting a species tree from a set of gene trees, as indicated recently in [Nature 2013].This paper focuses on two of the most well-known and widely used consensus tree methods: the greedy consensus tree and the frequency difference consensus tree. Given k conflicting trees each with n leaves, the previous fastest algorithms for these problems were O(k n^2) for the greedy consensus tree [J. ACM 2016] and O~(min{k n^2, k^2n}) for the frequency difference consensus tree [ACM TCBB 2016]. We improve these running times to O~(k n^{1.5}) and O~(k n) respectively.
展开▼
机译：共识树是一种系统发育树，可捕获一组冲突的系统发育树之间的相似性。计算共识树的问题是系统发育树重建的重要步骤。正如[Nature 2013]中最近指出的那样，它也是从一组基因树预测物种树的中心。本文着眼于两种最著名且使用最广泛的共识树方法：贪婪共识树和频率差异共识树。给定k个冲突的树，每个树有n个叶子，先前针对这些问题的最快算法是贪婪共识树的O（k n ^ 2）[J.频率差共识树[ACM TCBB 2016]和O〜（min {k n ^ 2，k ^ 2n}）。我们将这些运行时间分别提高到O〜（k n ^ {1.5}）和O〜（k n）。
展开▼
