JUCS - Journal of Universal Computer Science 23(9): 868-906, doi: 10.3217/jucs-023-09-0868
On the Sorting by Reversals and Transpositions Problem
expand article infoAndre Rodrigues Oliveira, Ulisses Dias§, Zanoni Dias
‡ University of Campinas, Campinas, Brazil§ University of Campinas, Limeira, Brazil
Open Access
Reversals and transpositions are two classic genome rearrangement operations. Reversals occur when a chromosome breaks at two locations called breakpoints and the DNA between the breakpoints is reversed. Transpositions occur when two adjacent blocks of elements exchange position. This paper presents a polynomial-time approximation algorithm for the Sorting by Reversals and Transpositions Problem. Our algorithm applies to both signed and unsigned versions of the problem, and it treats both cases in a unified manner. We prove an approximation factor of 2 for signed permutations and 2k for the unsigned case, where k is the approximation factor of the algorithm used for cycle decomposition, but in our practical experiments our algorithm found results with approximation ratio better than 1.5 in more than 99% of the signed permutations and better than 1.8 in more than 97% of the unsigned permutations. Our analysis also shows that our algorithm outperforms any other approach known to date.
approximation algorithms, genome rearrangement, sorting by reversals and transpositions