Perfect Sorting by Reversals is not Always Difficult

Christophe Paul 1 Sèverine Bérard 2 Anne Bergeron 3 Cedric Chauve 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
2 MAB - Méthodes et Algorithmes pour la Bioinformatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : This paper proposes new algorithms for computing pairwise rearrangement scenarios that conserve the combinatorial structure of genomes. More precisely, we investigate the problem of sorting signed permutations by reversals without breaking common intervals. We describe a combinatorial framework for this problem that allows to characterize classes of signed permutations for which one can compute in polynomial time a shortest reversal scenario that conserves all common intervals. In particular we define a class of permutations for which this computation can be done in linear time with a very simple algorithm that does not rely on the classical Hannenhalli-Pevzner theory for sorting by reversals. We apply these methods to the computation of rearrangement scenarios between permutations obtained from 16 synteny blocks of the X chromosomes of the human, mouse and rat.
Type de document :
Article dans une revue
IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2007, 4 (1), pp.12
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00111979
Contributeur : Christophe Paul <>
Soumis le : lundi 6 novembre 2006 - 17:28:23
Dernière modification le : jeudi 15 novembre 2018 - 20:27:22

Identifiants

  • HAL Id : lirmm-00111979, version 1

Collections

Citation

Christophe Paul, Sèverine Bérard, Anne Bergeron, Cedric Chauve. Perfect Sorting by Reversals is not Always Difficult. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2007, 4 (1), pp.12. 〈lirmm-00111979〉

Partager

Métriques

Consultations de la notice

158