An improved algorithm for the sorting by reversals and transpositions problem

Genome comparison among closely related species has revealed that organisms share large blocks of DNA sequence and that the ordering of these blocks may change across species. The main explanation is that genomes undergo large scale mutational events, also called rearrangements, during the evolutionary process. Reversals and transpositions are classic rearrangement operations. While a large body of literature exists on how to efficiently compute the reversal distance between genomes as well as to compute an approximate value for the transposition distance, these works generally do not take into account both reversals and transpositions. This paper presents a polynomial-time algorithm for the problem when both operations are allowed. Previous algorithms have approximation factor of 2, we do not improve this factor for every permutations. However, we show that the only step which does not guarantee an approximation ratio better than 1.75 occurs in rare situations. In addition, we carried out a batch of tests using 49,000 simulated instances and the greatest approximation factor we noticed was 1.8. Overall, we observed that our ratio is lower than 1.25 in more than 90% of the cases. When we consider only permutations whose sizes range from 200 to 500 (maximum size in our dataset), we observe that our ratio is lower than 1.25 in every case. We also show that our algorithm outperforms the state of the art by significant margins.