BMC Bioinformatics. 2013;14 Suppl 15(Suppl 15):S9. doi: 10.1186/1471-2105-14-S15-S9. Epub 2013 Oct 15.
We study the problem of sorting genomes under an evolutionary model that includes genomic rearrangements and segmental duplications. We propose an iterative algorithm to improve any initial evolutionary trajectory between two genomes in terms of parsimony. Our algorithm is based on a new graphical model, the trajectory graph, which models not only the final states of two genomes but also an existing evolutionary trajectory between them. We show that redundant rearrangements in the trajectory correspond to certain cycles in the trajectory graph, and prove that our algorithm converges to an optimal trajectory for any initial trajectory involving only rearrangements.
我们研究了在包含基因组重排和片段重复的进化模型下对基因组进行排序的问题。我们提出了一种迭代算法，根据简约性来改进两个基因组之间任何初始的进化轨迹。我们的算法基于一个新的图形模型，即轨迹图，它不仅对两个基因组的最终状态进行建模，还对它们之间的现有进化轨迹进行建模。我们表明，轨迹中的冗余重排在轨迹图中对应于某些循环，并证明我们的算法对于任何仅涉及重排的初始轨迹都收敛到最优轨迹。
