论文标题
共识树算法
An Algorithm for Consensus Trees
论文作者
论文摘要
我们考虑树共识问题，这是生物信息学中的重要问题。给定一个生根的树$ t $和另一棵树$ t $，一个人希望将兼容信息从$ t $到$ t $结合在一起。这个问题是树木改进问题中的一个子问题，称为RF最佳树的精致问题，由Christensen，Molloy，Molloy，Vachaspati和Warnow [Wabi'19]使用，他们使用Gawrychowski，Gawrychowski，Landau，Sung，Sung和Weimann [weimann [weimann] [1.18] $ of nime unlgrrychowski intherformant [wabi'18]。 n）$。我们为此问题提供了更快的算法，该算法在时间$ o（n \ log n）$中运行。我们的关键要素是基于摊销时间叶片计数器的两部分兼容性标准。尽管这是一个改进，但最快的解决方案是Jansson，Shen和Sung [Jacm'16]的算法，该算法在时间$ o（n）$中运行。
We consider the tree consensus problem, an important problem in bioinformatics. Given a rooted tree $t$ and another tree $T$, one would like to incorporate compatible information from $T$ to $t$. This problem is a subproblem in the tree refinement problem called the RF-Optimal Tree Refinement Problem defined by in Christensen, Molloy, Vachaspati and Warnow [WABI'19] who employ the greedy algorithm by Gawrychowski, Landau, Sung, and Weimann [ICALP'18] that runs in time $O(n^{1.5}\log n)$. We give a faster algorithm for this problem that runs in time $O(n\log n)$. Our key ingredient is a bipartition compatibility criteria based on amortized-time leaf counters. While this is an improvement, the fastest solution is an algorithm by Jansson, Shen, and Sung [JACM'16] which runs in time $O(n)$.
