Perfect DCJ rearrangement - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2008

Perfect DCJ rearrangement

Résumé

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
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

Citer

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 Consultations
255 Téléchargements

Altmetric

Partager

More