Papers › A new 1.375-approximation algorithm for Sorting By Transpositions
A new 1.375-approximation algorithm for Sorting By Transpositions
L. A. G. Silva, L. A. B. Kowada, N. R. Rocco, M. E. M. T. Walter
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
In genome rearrangements, the mutational event transposition swaps two adjacent blocks of genes in one chromosome. The Transposition Distance Problem (TDP) aims to find the minimum number of transpositions required to transform one chromosome into another, both represented as permutations. The TDP can be reduced to the problem of Sorting by Transpositions (SBT). SBT is 𝒩𝒫-hard and the best approximation algorithm with a $1.375$ ratio was proposed by Elias and Hartman. Their algorithm employs simplification, a technique used to transform an input permutation π into a simple permutation π̂, presumably easier to handle with. The permutation π̂ is obtained by inserting new symbols into π in a way that the lower bound of the transposition distance of π is kept on π̂. The simplification is guaranteed to keep the lower bound, not the transposition distance. In this paper, we first show that the algorithm of Elias and Hartman (EH algorithm) may require one extra transposition above the approximation ratio of $1.375$, depending on how the input permutation is simplified. Next, using an algebraic approach, we propose a new upper bound for the transposition distance and a new $1.375$-approximation algorithm to solve SBT skipping simplification and ensuring the approximation ratio of $1.375$ for all Sₙ. We implemented our algorithm and EH's. Regarding the implementation of the EH algorithm, two issues needed to be fixed. We tested both algorithms against all permutations of size n, 2≤n ≤12. The results show that the EH algorithm exceeds the approximation ratio of $1.375$ for permutations with a size greater than $7$. Finally, we investigate the performance of both implementations on longer permutations of maximum length $500$.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections