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), aproblem 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 withthe phylogenies presented in previous works. Finally, to facilitate phylogenetic studies based on the methods studied in this paper, wepresent a web tool for rearrangement-based phylogenetic inference using short operations, such as super short reversals.
Document type :
Journal articles
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01317003
Contributor : Marie-France Sagot <>
Submitted on : Friday, June 16, 2017 - 2:50:38 PM
Last modification on : Thursday, June 6, 2019 - 1:07:27 PM
Long-term archiving on : Wednesday, December 13, 2017 - 12:57:40 PM

File

SortingCircularPermutationsByS...
Files produced by the author(s)

Identifiers

Collections

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⟩

Share

Metrics

Record views

288

Files downloads

434