Skip to Main content Skip to Navigation
Conference papers

Perfect Sorting by Reversal is not Always Difficult

Sèverine Bérard 1 Anne Bergeron Cédric Chauve Christophe Paul 2
1 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper investigates the problem of conservation of combinatorial structures in genome rearrangement scenarios. We characterize a class of signed permutations for which one can compute in polynomial time a reversal scenario that conserves all common intervals, and that is parsimonious among such scenarios. Figeac and Varré (WABI 2004) announced that the general problem is NP-hard. We show that there exists a class of permutations for which this computation can be done in linear time with a very simple algorithm, and, for a larger class of signed permutations, the computation can be achieved in subquadratic time. We apply these methods to permutations obtained from the X chromosomes of the human, mouse and rat.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106465
Contributor : Christine Carvalho de Matos <>
Submitted on : Monday, October 16, 2006 - 8:29:27 AM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 7:42:21 PM

File

Identifiers

Collections

Citation

Sèverine Bérard, Anne Bergeron, Cédric Chauve, Christophe Paul. Perfect Sorting by Reversal is not Always Difficult. WABI: Workshop on Algorithms in Bioinformatics, Oct 2005, Mallorca, Spain. pp.228-238, ⟨10.1007/11557067_19⟩. ⟨lirmm-00106465⟩

Share

Metrics

Record views

200

Files downloads

239