Heuristics for the Sorting Signed Permutations by Reversals and Transpositions Problem

Author(s)

Brito, Klairton Lima ; Oliveira, Andre Rodrigues ; Dias, Ulisses ; Dias, Zanoni ; Jansson, J ; MartinVide, C ; VegaRodriguez, MA

• Document type: Journal article
• Source: ALGORITHMS FOR COMPUTATIONAL BIOLOGY (ALCOB 2018); v. 10849, p. 11-pg., 2018-01-01.

Abstract

We present two heuristics, Sliding Window and Look Ahead, to improve solutions for the Sorting Signed Permutations by Reversals and Transpositions Problem. To assess the heuristics, we implemented algorithms described in the literature to provide initial solutions. Despite the fact that we addressed a specific problem, both heuristics can be applied to many others within the area of genome rearrangement. When time is a crucial factor, Sliding Window is a better choice because it runs in linear time and improves the initial solutions in 76.4% of cases. If the quality of the solution is a priority, Look Ahead should be preferred because it improves the initial solutions in 97.6% of cases, but it runs in O(n(3) x alg(n)), where alg(n) is the complexity of the algorithm given as input. By using these heuristics one may find a good tradeoff between running time and solution improvement. (AU)

• FAPESP's process: 14/19401-8 - Genome rearrangement algorithms
• Grantee: Zanoni Dias
• Support Opportunities: Regular Research Grants
• 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