A 1.375-Approximation Algorithm for Sorting by Transpositions with Faster Running Time

Author(s)

Alexandrino, Alexsandro Oliveira ; Brito, Klairton Lima ; Oliveira, Andre Rodrigues ; Dias, Ulisses ; Dias, Zanoni ; Scherer, NM ; DeMelo-Minardi, RC

• Document type: Journal article
• Source: ADVANCES IN BIOINFORMATICS AND COMPUTATIONAL BIOLOGY, BSB 2022; v. 13523, p. 11-pg., 2022-01-01.

Abstract

Sorting Permutations by Transpositions is a famous problem in the Computational Biology field. This problem is NP-Hard, and the best approximation algorithm, proposed by Elias and Hartman in 2006, has an approximation factor of 1.375. Since then, several researchers have proposed modifications to this algorithm to reduce the time complexity. More recently, researchers showed that the algorithm proposed by Elias and Hartman might need one more operation above the approximation ratio and presented a new 1.375-approximation algorithm using an algebraic approach that corrected this issue. This algorithm runs in O(n(6)) time. In this paper, we present an efficient way to fix Elias and Hartman algorithm that runs in O(n(5)). By comparing the three approximation algorithms with all permutations of size n <= 12, we also show that our algorithm finds the exact distance in more instances than the previous two algorithms. (AU)

• FAPESP's process: 19/27331-3 - Sorting by genome rearrangements problems
• Grantee: André Rodrigues Oliveira
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• 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: 13/08293-7 - CCES - Center for Computational Engineering and Sciences
• Grantee: Munir Salomao Skaf
• Support Opportunities: Research Grants - Research, Innovation and Dissemination Centers - RIDC