On the sorting by reversals and transpositions problem

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. © 2017,iicm. all rights reserved.