Alexeev Nikita, Avdeyev Pavel, Alekseyev Max A
The George Washington University, Washington, DC, USA.
BMC Bioinformatics. 2016 Nov 11;17(Suppl 14):418. doi: 10.1186/s12859-016-1263-7.
Genome median and genome halving are combinatorial optimization problems that aim at reconstruction of ancestral genomes by minimizing the number of evolutionary events between them and genomes of the extant species. While these problems have been widely studied in past decades, their solutions are often either not efficient or not biologically adequate. These shortcomings have been recently addressed by restricting the problems solution space.
We show that the restricted variants of genome median and halving problems are, in fact, closely related. We demonstrate that these problems have a neat topological interpretation in terms of embedded graphs and polygon gluings. We illustrate how such interpretation can lead to solutions to these problems in particular cases.
This study provides an unexpected link between comparative genomics and topology, and demonstrates advantages of solving genome median and halving problems within the topological framework.
基因组中位数和基因组减半是组合优化问题，旨在通过最小化它们与现存物种基因组之间的进化事件数量来重建祖先基因组。尽管在过去几十年中对这些问题进行了广泛研究，但其解决方案往往要么效率不高，要么在生物学上不合适。最近通过限制问题的解空间解决了这些缺点。
我们表明，基因组中位数和减半问题的受限变体实际上密切相关。我们证明这些问题在嵌入图和多边形胶合方面有简洁的拓扑解释。我们说明了这种解释如何在特定情况下导致这些问题的解决方案。
本研究在比较基因组学和拓扑学之间提供了意想不到的联系，并证明了在拓扑框架内解决基因组中位数和减半问题的优势。
