Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 23 / Issue 9

available in:   PDF (312 kB) PS (428 kB)
Similar Docs BibTeX   Write a comment
Links into Future


On the Sorting by Reversals and Transpositions Problem

Andre Rodrigues Oliveira (University of Campinas, Brazil)

Ulisses Dias (University of Campinas, Brazil)

Zanoni Dias (University of Campinas, Brazil)

Abstract: 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.

Keywords: approximation algorithms, genome rearrangement, sorting by reversals and transpositions

Categories: F.2.0, G.2.3