Skip to Main content Skip to Navigation
Journal articles

Computation of Perfect DCJ Rearrangement Scenarios with Linear and Circular Chromosomes

Abstract : 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 revervals are hard ones for DCJ, and {\em vice versa}.
Document type :
Journal articles
Complete list of metadatas
Contributor : Christophe Paul <>
Submitted on : Monday, November 16, 2009 - 8:48:09 PM
Last modification on : Friday, December 18, 2020 - 5:12:01 PM

Links full text



Sèverine Bérard, Annie Chateau, Cedric Chauve, Christophe Paul, Eric Tannier. Computation of Perfect DCJ Rearrangement Scenarios with Linear and Circular Chromosomes. Journal of Computational Biology, Mary Ann Liebert, 2009, 16 (10), pp.1287-1309. ⟨10.1089/cmb.2009.0088⟩. ⟨lirmm-00432670⟩



Record views