Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Sorting Circular Permutations by Super Short Reversals

Full text
Author(s):
Galvao, Gustavo Rodrigues ; Baudet, Christian ; Dias, Zanoni
Total Authors: 3
Document type: Journal article
Source: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS; v. 14, n. 3, p. 620-633, MAY-JUN 2017.
Web of Science Citations: 2
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. (AU)

FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
Grantee:Munir Salomao Skaf
Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 14/04718-6 - Algorithms for rearrangement sorting problem
Grantee:Gustavo Rodrigues Galvão
Support Opportunities: Scholarships in Brazil - Doctorate