The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in $O(n\log n)$ Time

Jesun Sahariar Firoz, Masud Hasan, Ashik Zinnat Khan +1

Sorting a Permutation by Transpositions (SPbT) is an important problem in Bioinformtics. In this paper, we improve the running time of the best known approximation algorithm for SP…