Bérard Sèverine, Chateau Annie, Chauve Cedric, Paul Christophe, Tannier Eric
Université Montpellier 2, UMR AMAP, Montpellier, France.
J Comput Biol. 2009 Oct;16(10):1287-309. doi: 10.1089/cmb.2009.0088.
We study the problem of transforming a multichromosomal genome into another using Double Cut-and-Join (DCJ) operations, which simulates several types of rearrangements, as reversals, translocations, and block-interchanges. We introduce the notion of a DCJ scenario that does not break families of common intervals (groups of genes co-localized in both genomes). Such scenarios are called perfect, and their properties are well known when the only considered rearrangements are reversals. We show that computing the minimum perfect DCJ rearrangement scenario is NP-hard, and describe an exact algorithm which exponential running time is bounded in terms of a specific pattern used in the NP-completeness proof. The study of perfect DCJ rearrangement leads to some surprising properties. The DCJ model has often yielded algorithmic problems which complexities are comparable to the reversal-only model. In the perfect rearrangement framework, however, while perfect sorting by reversals is NP-hard if the family of common intervals to be preserved is nested, we show that finding a shortest perfect DCJ scenario can be answered in polynomial time in this case. Conversely, while perfect sorting by reversals is tractable when the family of common intervals is weakly separable, we show that the corresponding problem is still NP-hard in the DCJ case. This shows that despite the similarity of the two operations, easy patterns for reversals are hard ones for DCJ, and vice versa.
我们研究了使用双切割与连接（DCJ）操作将多染色体基因组转化为另一个基因组的问题，该操作模拟了几种类型的重排，如反转、易位和块交换。我们引入了一种DCJ场景的概念，该场景不会破坏公共区间家族（在两个基因组中共同定位的基因群）。这样的场景被称为完美场景，当仅考虑的重排是反转时，其性质是众所周知的。我们表明，计算最小完美DCJ重排场景是NP难的，并描述了一种精确算法，其指数运行时间根据NP完全性证明中使用的特定模式来界定。对完美DCJ重排的研究导致了一些令人惊讶的性质。DCJ模型经常产生一些算法问题，其复杂度与仅反转模型相当。然而，在完美重排框架中，如果要保留的公共区间家族是嵌套的，那么通过反转进行完美排序是NP难的，而在这种情况下，我们表明可以在多项式时间内找到最短的完美DCJ场景。相反，当公共区间家族是弱可分离时，通过反转进行完美排序是可处理的，而我们表明在DCJ情况下相应的问题仍然是NP难的。这表明，尽管这两种操作相似，但反转的简单模式对于DCJ来说是困难的，反之亦然。
