| Perfect DCJ rearrangement | |
Abstract/OtherAbstract
:
|
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. |
Authors
:
|
Chateau, Annie, Chauve, Cedric, Bérard, Sèverine, Tannier, Eric, Paul, Christophe |
Related Documents
:
|
0033540907 - Exotic diseases are common 0034123807 - 01698 0007612927 - Adaptive community forest management: an alternate paradigm |
Contributors
:
|
- |
Publication Detail
:
|
Publisher : HAL - CCSD Type : proceeding with peer review Format : - |
Date Detail
:
|
2008-11-24 |
Subject
:
|
Computer Science/Bioinformatics, Computer Science/Computational Complexity, Life Sciences/Quantitative Methods, double-cut and join rearrangement scenario |
Coverage
:
|
- |
Relation
:
|
http://hal.inria.fr/docs/00/32/72/58/PDF/Berard_et_al_final.pdf |
Source
:
|
- |
Copyright Information
:
|
- |
Other Details
:
|
Languages : EN |
Export Citation
:
|
APA/MLA Format Download EndNote Download BibTex |
Previous Document: The Ethics of Hope: Newspaper Reporting of Chemotherapy
Next Document: Non-directive Counselling and Cognitive Behaviour Therapy Have Short-Term Benefits Over Usual GP Car...