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 also finds applications in predicting a species tree from a set of gene trees. This paper focuses on two of the most well-known and widely used oconsensus 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 $\tilde O(\min \{ k n^2, k^2n\})$ for the frequency difference consensus tree [ACM TCBB 2016]. We improve these running times to $\tilde O(k n^{1.5})$ and $\tilde O(k n)$ respectively.
翻译：协商一致树是一棵凝聚的植物树,它捕捉到一系列相互冲突的植物基因树之间的相似性。计算协商一致树的问题是植物基因树重建的一个重要步骤。它也发现从一组基因树中预测物种树的应用。本文侧重于两种最广为人知和广泛使用的同系树方法:贪婪的协商一致树和频率差异的协商一致树。鉴于每棵树的叶叶相冲突,这些问题的最快算法是:贪婪的协商一致树[J.ACM 2016] $O(k n ⁇ 2美元)和频率差异一致树[ACM TCB 2016]$\tilde O(k n ⁇ 2, k ⁇ 2, k ⁇ 2n ⁇ )$。我们将这些时间分别改进为$\tilde O(k n ⁇ 1.5美元) 和 $\tilde O(k n美元) 。
相关内容
微信扫码咨询专知VIP会员