论文标题
最佳匹配图的修改问题的复杂性
Complexity of modification problems for best match graphs
论文作者
论文摘要
最佳匹配图（BMG）是顶点颜色的有向图，这些图被引入，以模拟来自不同物种（颜色）的基因关系（颜色）的关系，并给定假定未知的基础进化树。在现实生活中，从序列相似性数据估算了BMG。测量噪声和近似误差通常会导致经验确定的图表，这些图通常违反了BMG的特征性能。 BMG的弧修改问题旨在纠正此类违规行为，从而提供一种方法来改善最佳匹配数据的初始估计。我们在这里表明，BMG的弧删除，弧完成和弧编辑问题是NP组件的，并且可以作为整数线性程序制定和求解。为此，我们提供了BMG的新颖特征，该表征在三倍（三片叶子上的二进制树）和具有两种颜色的BMG的特征在于禁止的子图。
Best match graphs (BMGs) are vertex-colored directed graphs that were introduced to model the relationships of genes (vertices) from different species (colors) given an underlying evolutionary tree that is assumed to be unknown. In real-life applications, BMGs are estimated from sequence similarity data. Measurement noise and approximation errors usually result in empirically determined graphs that in general violate characteristic properties of BMGs. The arc modification problems for BMGs aim at correcting such violations and thus provide a means to improve the initial estimates of best match data. We show here that the arc deletion, arc completion and arc editing problems for BMGs are NP-complete and that they can be formulated and solved as integer linear programs. To this end, we provide a novel characterization of BMGs in terms of triples (binary trees on three leaves) and a characterization of BMGs with two colors in terms of forbidden subgraphs.
