Perfect DCJ rearrangement

Annie Château 1, * Cedric Chauve 2, 3 Sèverine Bérard 1 Eric Tannier 4 Christophe Paul 5
* Auteur correspondant
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
5 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. 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.
Type de document :
Communication dans un congrès
C.E. Nelson; S. Vialette. RECOMB Comparative Genomics, Oct 2008, Paris, France. Springer-Verlag, 6th International Workshop on RECOMB Comparative Genomics, LNCS (5267), pp.158-169, 2008, Comparative Genomics. 〈http://igm.univ-mlv.fr/RCG08/〉. 〈10.1007/978-3-540-87989-3_12〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00327258
Contributeur : Annie Chateau <>
Soumis le : mercredi 8 octobre 2008 - 16:32:03
Dernière modification le : mardi 9 octobre 2018 - 14:56:10
Document(s) archivé(s) le : lundi 8 octobre 2012 - 14:10:14

Fichier

Berard_et_al_final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Annie Château, Cedric Chauve, Sèverine Bérard, Eric Tannier, Christophe Paul. Perfect DCJ rearrangement. C.E. Nelson; S. Vialette. RECOMB Comparative Genomics, Oct 2008, Paris, France. Springer-Verlag, 6th International Workshop on RECOMB Comparative Genomics, LNCS (5267), pp.158-169, 2008, Comparative Genomics. 〈http://igm.univ-mlv.fr/RCG08/〉. 〈10.1007/978-3-540-87989-3_12〉. 〈lirmm-00327258〉

Partager

Métriques

Consultations de la notice

499

Téléchargements de fichiers

201