Computation of Perfect DCJ Rearrangement Scenarios with Linear and Circular Chromosomes

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}.
Type de document :
Article dans une revue
Journal of Computational Biology, Mary Ann Liebert, 2009, 16 (10), pp.1287-1309
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00432670
Contributeur : Christophe Paul <>
Soumis le : lundi 16 novembre 2009 - 20:48:09
Dernière modification le : jeudi 28 juin 2018 - 14:36:01

Identifiants

  • HAL Id : lirmm-00432670, version 1

Citation

Sèverine Bérard, Annie Château, 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〉

Partager

Métriques

Consultations de la notice

476