Perfect Sorting by Reversal is not Always Difficult - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Communication Dans Un Congrès Année : 2005

Perfect Sorting by Reversal is not Always Difficult

Anne Bergeron
  • Fonction : Auteur
Cédric Chauve
  • Fonction : Auteur
Christophe Paul

Résumé

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.

Domaines

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

Dates et versions

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

Identifiants

Citer

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⟩
107 Consultations
259 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More