Perfect Sorting by Reversal is not Always Difficult - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2005

Perfect Sorting by Reversal is not Always Difficult

Anne Bergeron
  • Function : Author
Cédric Chauve
  • Function : Author
Christophe Paul


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.


Other [cs.OH]
Fichier principal
Vignette du fichier
D525.PDF (144.41 Ko) Télécharger le fichier

Dates and versions

lirmm-00106465 , version 1 (16-10-2006)



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⟩
109 View
265 Download



Gmail Mastodon Facebook X LinkedIn More