Analysis of genomes evolving by inversions leads to a general
combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of
sorting a permutation by a minimum number of reversals.
This combinatorial problem has a long history, and a number of other
motivations. It was studied in a great detail recently in
computational molecular biology. Following a series of preliminary results,
Hannenhalli and Pevzner developed the first exact polynomial time algorithm
for the problem of sorting signed permutations by reversals, and a polynomial
time algorithm for a special case of unsigned permutations. The best known
approximation algorithm for MIN-SBR, due to Christie, gives a performance
ratio of 1.5. In this paper, by exploiting the polynomial time algorithm
for sorting signed permutations and by developing a new approximation
algorithm for maximum cycle decomposition of breakpoint graphs, we improve
the performance ratio for MIN-SBR to 1.375.
Besides its biological and combinatorial importance, better approximation
algorithms for MIN-SBR have become particularly challenging recently because
this problem has been proven to NP-hard by Caprara, and MAX-SNP hard by
Berman and Karpinski, excluding thus an existence of a polynomial time
approximation scheme (PTAS) for that problem.