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

On the Sorting by Reversals and Transpositions Problem

Oliveira, Andre Rodrigues [1] ; Dias, Ulisses [2] ; Dias, Zanoni [1]
Total Authors: 3
[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil
[2] Univ Estadual Campinas, Sch Technol, Limeira - Brazil
Total Affiliations: 2
Document type: Journal article
Source: JOURNAL OF UNIVERSAL COMPUTER SCIENCE; v. 23, n. 9, p. 868-906, 2017.
Web of Science Citations: 1

Reversals and transpositions are two classic genome rearrangement operations. Reversals occur when a chromosome breaks at two locations called breakpoints and the DNA between the breakpoints is reversed. Transpositions occur when two adjacent blocks of elements exchange position. This paper presents a polynomial-time approximation algorithm for the Sorting by Reversals and Transpositions Problem. Our algorithm applies to both signed and unsigned versions of the problem, and it treats both cases in a unified manner. We prove an approximation factor of 2 for signed permutations and 2k for the unsigned case, where k is the approximation factor of the algorithm used for cycle decomposition, but in our practical experiments our algorithm found results with approximation ratio better than 1.5 in more than 99% of the signed permutations and better than 1.8 in more than 97% of the unsigned permutations. Our analysis also shows that our algorithm outperforms any other approach known to date. (AU)

FAPESP's process: 14/19401-8 - Genome rearrangement algorithms
Grantee:Zanoni Dias
Support type: Regular Research Grants
FAPESP's process: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
Grantee:Munir Salomao Skaf
Support type: Research Grants - Research, Innovation and Dissemination Centers - RIDC
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support type: Research Projects - Thematic Grants