Computation of Perfect DCJ Rearrangement Scenarios with Linear and Circular Chromosomes

Sèverine Bérard 1, 2 Annie Chateau 2 Cedric Chauve 3 Christophe Paul 4 Eric Tannier 5
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432670
Contributor : Christophe Paul <>
Submitted on : Monday, November 16, 2009 - 8:48:09 PM
Last modification on : Wednesday, August 28, 2019 - 1:34:00 PM

Identifiers

  • HAL Id : lirmm-00432670, version 1

Citation

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. ⟨lirmm-00432670⟩

Share

Metrics

Record views

565