The problem of finding a common refinement of a set of rooted trees with common leaf set $L$ appears naturally in mathematical phylogenetics whenever poorly resolved information on the same taxa from different sources is to be reconciled. This constitutes a special case of the well-studied supertree problem, where the leaf sets of the input trees may differ. Algorithms that solve the rooted tree compatibility problem are of course applicable to this special case. However, they require sophisticated auxiliary data structures and have a running time of at least $O(k|L|\log^2(k|L|))$ for $k$ input trees. Here, we show that the problem can be solved in $O(k|L|)$ time using a simple bottom-up algorithm called LinCR. An implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda.
翻译：找到一套用普通叶子固定的根树的共同精细化问题,只要需要调和不同来源的关于同一分类群的解决不力的信息,就自然地出现在数学血浆中。这是研究周密的超级树问题的一个特例,输入树的叶组可能不同。解决根树兼容性问题的分类法当然适用于这一特例。然而,它们需要复杂的辅助数据结构,并且至少运行时间为$O(k ⁇ L ⁇ log ⁇ 2(k ⁇ L ⁇ ))美元投入树。在这里,我们表明问题可以用名为LinCR的简单自下而上的算法解决。在Python的LinCR可免费在https://github.com/david-schaller/tralda查阅。
相关内容
微信扫码咨询专知VIP会员