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.
翻译:最佳匹配图( BMG) 是基于图形的正弦学检测中的关键中间体, 并包含大量有关基因树的信息。 我们提供了一种近立方算法, 以确定 BMG 是否是二进制解释的, 也就是说, 它是否可以用完全解决的基因树来解释, 如果可以解释, 建造这样的树 。 此外, 我们显示所有这些二进制树都是独特的二进制可溶树( BRT ) 的精细, 一般来说, 是对BMG 中同样解决最少的树的实质性改进 。 最后, 我们显示, 将任意的脊椎色图编辑为二进制可解决的BMG 的问题是完整的, 并为此项任务提供一个整形线性程序配方 。