A 1.375-Approximation Algorithm for Sorting by Transpositions with Faster Running Time - Alexandrino, Alexsandro Oliveira; Brito, Klairton Lima; Oliveira, Andre Rodrigues; Dias, Ulisses; Dias, Zanoni (Anais do Simpósio Brasileiro de Bioinformática (BSB); 2022: Anais do XV Simpósio Brasileiro de Bioinformática, 2022)
Sorting Permutations by Transpositions is a famous problem in the Computational Biology ﬁeld. 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 ﬁx 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.