Sorting Signed Circular Permutations by Super Short Reversals

Abstract : We consider the problem of sorting a circular permutation by reversals of length at most 2, a problem that finds application in comparative genomics. Polynomial-time solutions for the unsigned version of this problem are known, but the signed version remained open. In this paper, we present the first polynomial-time solution for the signed version of this problem. Moreover, we perform an experiment for inferring distances and phylogenies for published Yersinia genomes and compare the results with the phylogenies presented in previous works.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-01316993
Contributor : Marie-France Sagot <>
Submitted on : Monday, June 12, 2017 - 12:17:52 PM
Last modification on : Thursday, June 6, 2019 - 1:07:31 PM
Long-term archiving on : Thursday, September 14, 2017 - 12:14:38 PM

File

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

Identifiers

Collections

Citation

Gustavo Galvão, Christian Baudet, Zanoni Dias. Sorting Signed Circular Permutations by Super Short Reversals. 11th International Symposium on Bioinformatics Research and Applications, Jun 2015, Norfolk, Virginia, United States. pp.272-283, ⟨10.1007/978-3-319-19048-8_23⟩. ⟨hal-01316993⟩

Share

Metrics

Record views

238

Files downloads

285