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.
Type de document :
Communication dans un congrès
WABI: Workshop on Algorithms in Bioinformatics, Oct 2005, Mallorca, Spain. 5th International Workshop on Algorithms in Bioinformatics, LNCS (3692), pp.228-238, 2005, Algorithms in Bioinformatics. 〈10.1007/11557067_19〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00106465
Contributeur : Christine Carvalho de Matos <>
Soumis le : lundi 16 octobre 2006 - 08:29:27
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mardi 6 avril 2010 - 19:42:21

Fichier

Identifiants

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. 5th International Workshop on Algorithms in Bioinformatics, LNCS (3692), pp.228-238, 2005, Algorithms in Bioinformatics. 〈10.1007/11557067_19〉. 〈lirmm-00106465〉

Partager

Métriques

Consultations de la notice

96

Téléchargements de fichiers

104