Multichromosomal median and halving problems under different genomic distances

Eric Tannier 1, 2, * Chunfang Zheng 3 David Sankoff 3
* Corresponding author
2 BAMBOO - An algorithmic view on genomes, cells, and environments
Inria Grenoble - Rhône-Alpes, LBBE - Laboratoire de Biométrie et Biologie Evolutive - UMR 5558
Abstract : Background
Genome median and genome halving are combinatorial optimization problems that aim at reconstructing ancestral genomes as well as the evolutionary events leading from the ancestor to extant species. Exploring complexity issues is a first step towards devising efficient algorithms. The complexity of the median problem for unichromosomal genomes (permutations) has been settled for both the breakpoint distance and the reversal distance. Although the multichromosomal case has often been assumed to be a simple generalization of the unichromosomal case, it is also a relaxation so that complexity in this context does not follow from existing results, and is open for all distances.
Results
We settle here the complexity of several genome median and halving problems, including a surprising polynomial result for the breakpoint median and guided halving problems in genomes with circular and linear chromosomes, showing that the multichromosomal problem is actually easier than the unichromosomal problem. Still other variants of these problems are NP-complete, including the DCJ double distance problem, previously mentioned as an open question. We list the remaining open problems.
Conclusion
This theoretical study clears up a wide swathe of the algorithmical study of genome rearrangements with multiple multichromosomal genomes.
Liste complète des métadonnées

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-00784456
Contributor : Ed. Bmc <>
Submitted on : Monday, February 4, 2013 - 1:12:11 PM
Last modification on : Thursday, March 21, 2019 - 2:51:28 PM
Document(s) archivé(s) le : Sunday, May 5, 2013 - 7:30:08 AM

Files

Identifiers

Collections

Citation

Eric Tannier, Chunfang Zheng, David Sankoff. Multichromosomal median and halving problems under different genomic distances. BMC Bioinformatics, BioMed Central, 2009, 10 (1), pp.120. ⟨10.1186/1471-2105-10-120⟩. ⟨hal-00784456⟩

Share

Metrics

Record views

293

Files downloads

134