Recently, a new approach to analyze genomes evolving
was proposed which is based on comparison
of gene orders versus traditional comparison of
DNA sequences (Sankoff et al, 1992).
The approach is based on the global rearrangements
(e.g., inversions and transpositions of fragments).
Analysis of genomes evolving by inversions
and transpositions leads to a combinatorial
problem of sorting by reversals and transpositions,
i.e., sorting of a permutation using reversals
and transpositions of arbitrary fragments.
%The problem is conjectured as NP-hard.
We study sorting of signed permutations by reversals
and transpositions, a problem which adequately
models genome rearrangements, as the genes
in DNA are oriented.
We establish a lower bound and
give a 2-approximation algorithm for the problem.