Perfect DCJ rearrangement

Annie Chateau 1, * Cedric Chauve 2, 3 Sèverine Bérard 1 Eric Tannier 4 Christophe Paul 5
* Corresponding author
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.
Complete list of metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00327258
Contributor : Annie Chateau <>
Submitted on : Wednesday, October 8, 2008 - 4:32:03 PM
Last modification on : Tuesday, September 17, 2019 - 5:26:06 PM
Long-term archiving on : Monday, October 8, 2012 - 2:10:14 PM

File

Berard_et_al_final.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

552

Files downloads

386