Sorting Circular Permutations by Super Short Reversals

Abstract : We consider the problem of sorting a circular permutation by super short reversals (i.e., reversals of length at most 2), a problem that finds application in comparative genomics. Polynomial-time solutions to the unsigned version of this problem are known, but the signed version remained open. In this paper, we present the first polynomial-time solution to the signed version of this problem. Moreover, we perform experiments for inferring phylogenies of two different groups of bacterial species and compare our results with the phylogenies presented in previous works. Finally, to facilitate phylogenetic studies based on the methods studied in this paper, we present a web tool for rearrangement-based phylogenetic inference using short operations, such as super short reversals.
Type de document :
Article dans une revue
IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2017, 14 (3), pp.620-633. 〈http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7374688〉. 〈10.1109/TCBB.2016.2515594〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01317003
Contributeur : Marie-France Sagot <>
Soumis le : vendredi 16 juin 2017 - 14:50:38
Dernière modification le : jeudi 19 avril 2018 - 14:49:47
Document(s) archivé(s) le : mercredi 13 décembre 2017 - 12:57:40

Fichier

SortingCircularPermutationsByS...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Gustavo Rodrigues Galvao, Christian Baudet, Zanoni Dias. Sorting Circular Permutations by Super Short Reversals. IEEE/ACM Transactions on Computational Biology and Bioinformatics, Institute of Electrical and Electronics Engineers, 2017, 14 (3), pp.620-633. 〈http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=7374688〉. 〈10.1109/TCBB.2016.2515594〉. 〈hal-01317003〉

Partager

Métriques

Consultations de la notice

224

Téléchargements de fichiers

46