论文标题
最佳匹配图与二进制树
Best Match Graphs with Binary Trees
论文作者
论文摘要
最佳匹配图（BMG）是基于图的矫正检测中的关键中间体，并在基因树上包含大量信息。我们提供了一种近乎立方体的算法，以确定BMG是否可以解释BMG，即是否可以通过完全分辨的基因树来解释它，如果是的，则可以构造这种树。此外，我们表明所有这些二进制树都是独特的二进制可辨别树（BRT）的改进，通常，它是对BMG的最不可分割的树的实质性改进。最后，我们表明，将任意的顶点色图编辑为二进制BMG的问题是NP完整的，并为此任务提供了整数线性程序公式。
Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG is binary-explainable, i.e., whether it can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-resolvable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.
