论文标题
最佳匹配图中错误的矫正分配的完全表征
Complete Characterization of Incorrect Orthology Assignments in Best Match Graphs
论文作者
论文摘要
基因组规模的矫正分配通常基于相互的最佳匹配。在没有水平基因转移（HGT）的情况下，每对直系同源物都形成相互的最佳匹配。因此，错误的矫正分配始终是倒数最佳匹配图中的误报。我们考虑重复/损失方案，并表征明确的假阳性（U-FP）矫正分配，也就是说，在最佳匹配图（BMG）中的边缘（BMG）无法与任何解释BMG的基因树相对应。此外，我们提供了多项式时间算法，以识别BMG中的所有U-FP矫正分配。模拟表明，可以以这种方式检测到所有不正确的矫正分配中至少$ 75 \％$。所有结果都仅依赖于BMG的结构，而不仅依赖于有关潜在基因或物种树木的任何先验知识。
Genome-scale orthology assignments are usually based on reciprocal best matches. In the absence of horizontal gene transfer (HGT), every pair of orthologs forms a reciprocal best match. Incorrect orthology assignments therefore are always false positives in the reciprocal best match graph. We consider duplication/loss scenarios and characterize unambiguous false-positive (u-fp) orthology assignments, that is, edges in the best match graphs (BMGs) that cannot correspond to orthologs for any gene tree that explains the BMG. Moreover, we provide a polynomial-time algorithm to identify all u-fp orthology assignments in a BMG. Simulations show that at least $75\%$ of all incorrect orthology assignments can be detected in this manner. All results rely only on the structure of the BMGs and not on any a priori knowledge about underlying gene or species trees.
