An important problem in computational molecular biology is the genome rearrangement using reversals and transpositions. Analysis
of genome evolving by inversions and transpositions leads to a combinatorial optimization problem of sorting by reversals
and transpositions, i.e., sorting of a permutation using reversals and transpositions of arbitrary fragments. The reversal
operation works on a single segment of the genome by reversing the selected segment. Two kinds of transpositions have been
studied in the literature. The first kind of transposition operation deletes a segment of the genome and insert it into another
position in the genome. The second kind of transposition operation deletes a segment of the genome and insert its inverse
into another position in the genome. Both transposition operations can be viewed as operations working on two consecutive
segments. A third transposition operation working on two consecutive segments is introduced which, together with reversal
and the first two kinds of transposition operations, forms the complete set of operations on two consecutive segments. In
this paper, we study the sorting of a signed permutation by reversals and transpositions. By allowing only the first kind
of transpositions, or the first two kinds of transpositions, or all three kinds of transpositions, we have three problem models.
After establishing a common lower bound on the numbers of operations needed, we present a unified 2-approximation algorithm
for all these problems. Finally, we present a better 1.75-approximation for the third problem.
This research was supported in part by the Army Research Office grant DAAH04-96-10233.