Simonaitis Pijus, Chateau Annie, Swenson Krister M
1CNRS, LIRMM, Université Montpellier, 161 Rue Ada, 34392 Montpellier, France.
2Institut de Biologie Computationnelle (IBC), Montpellier, France.
Algorithms Mol Biol. 2019 Jul 19;14:15. doi: 10.1186/s13015-019-0149-4. eCollection 2019.
This paper generalizes previous studies on genome rearrangement under biological constraints, using double cut and join (DCJ). We propose a model for weighted DCJ, along with a family of optimization problems called -MCPS (Minimum Cost Parsimonious Scenario), that are based on labeled graphs. We show how to compute solutions to general instances of -MCPS, given an algorithm to compute -MCPS on a circular genome with exactly one occurrence of each gene. These general instances can have an arbitrary number of circular and linear chromosomes, and arbitrary gene content. The practicality of the framework is displayed by presenting polynomial-time algorithms that generalize the results of Bulteau, Fertin, and Tannier on the Sorting by wDCJs and indels in intergenes problem, and that generalize previous results on the Minimum Local Parsimonious Scenario problem.
本文使用双切割与连接（DCJ）方法，对先前关于生物约束下基因组重排的研究进行了推广。我们提出了一种加权DCJ模型，以及一族基于标记图的被称为 -MCPS（最小成本简约场景）的优化问题。我们展示了如何在给定一种算法来计算每个基因恰好出现一次的环状基因组上的 -MCPS的情况下，计算 -MCPS一般实例的解。这些一般实例可以有任意数量的环状和线性染色体以及任意的基因内容。通过给出多项式时间算法展示了该框架的实用性，这些算法推广了Bulteau、Fertin和Tannier在基因间区域通过加权DCJ和插入缺失进行排序问题上的结果，以及推广了先前关于最小局部简约场景问题的结果。
