An algebraic 1.375-approximation algorithm for the Transposition Distance Problem

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. TDP is $\mathcal{NP}$-hard and the best approximation algorithm with a $1.375$ ratio was proposed in 2006 by Elias and Hartman. Their algorithm employs simplification, a technique used to transform an input permutation $\pi$ into a simple permutation $\hat{\pi}$, presumably easier to handle with. $\hat{\pi}$ is obtained by inserting new symbols into $\pi$ in a way that the lower bound of the transposition distance of $\pi$ is kept on $\hat{\pi}$. A sequence of transpositions sorting $\hat{\pi}$ can be mimicked to sort $\pi$. First, we show that the algorithm of Elias and Hartman may require one extra transposition above the approximation ratio of $1.375$, depending on how the input permutation is simplified. Next, using an algebraic formalism, a new upper bound for the transposition distance is proposed. From this result, a new $1.375$-approximation algorithm is proposed to solve TDP skipping simplification and ensuring the approximation ratio of $1.375$ for all the permutations in the Symmetric Group $S_n$. Implementations of our algorithm and of Elias and Hartman were tested against short permutations of maximum length $12$. The results show that our algorithm, in addition to keeping the approximation below the $1.375$ ratio, outperforms the algorithm of Elias and Hartman in relation to the rate of the correct answers, i.e., the computed distances that are equal to the transposition distance.