Perfect DCJ rearrangement - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2008

Perfect DCJ rearrangement

Abstract

We study the problem of transforming a multichromosomal genome into another using Double-Cut-and-Join (DCJ) operations. We introduce the notion of DCJ scenario that does not break families of common intervals (groups of genes co-localized in both genomes). Such scenarios are called perfect, and generalize the notion of perfect reversal scenarios. While perfect sorting by reversals is NP-hard if the family of common intervals is nested, we show that finding a shortest perfect DCJ scenario can be answered in polynomial time in this case. Moreover, while perfect sorting by reversals is easy when the family of common intervals is weakly separable, we show that the corresponding problem is NP-hard in the DCJ case. These contrast with previous comparisons between the reversal and DCJ models, that showed that most problems have similar complexity in both models.
Fichier principal
Vignette du fichier
Berard_et_al_final.pdf (146.01 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00327258 , version 1 (08-10-2008)

Identifiers

Cite

Annie Chateau, Cedric Chauve, Sèverine Bérard, Eric Tannier, Christophe Paul. Perfect DCJ rearrangement. RECOMB-CG: Comparative Genomics, Oct 2008, Paris, France. pp.158-169, ⟨10.1007/978-3-540-87989-3_12⟩. ⟨lirmm-00327258⟩
264 View
255 Download

Altmetric

Share

More