On the Sorting by Reversals and Transpositions Problem

Author(s)

Oliveira, Andre Rodrigues ^[1] ; Dias, Ulisses ^[2] ; Dias, Zanoni ^[1]

Affiliation

^[1] Univ Estadual Campinas, Inst Comp, Campinas, SP - Brazil

^[2] Univ Estadual Campinas, Sch Technol, Limeira - Brazil

• Document type: Journal article
• Source: JOURNAL OF UNIVERSAL COMPUTER SCIENCE; v. 23, n. 9, p. 868-906, 2017.
• Web of Science Citations: 1

Abstract

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: 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: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
• Grantee: Flávio Keidi Miyazawa
• Support Opportunities: Research Projects - Thematic Grants
• FAPESP's process: 14/19401-8 - Genome rearrangement algorithms
• Grantee: Zanoni Dias
• Support Opportunities: Regular Research Grants