Signed genome rearrangement by reversals and transpositions: Models and approximations

An important problem in computational biology is the genome rearrangement using reversals and transpositions. Analysis of genome evolving by reversals 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 operations delete a segment of the genome and insert it into another position in the genome. The second kind of transposition operations delete 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. In this paper, we introduce a third transposition operation which works on two consecutive segments and study sorting of a signed permutation by reversals and transpositions. By allowing reversals and the first kind of transpositions, or reversals and the first two kinds of transpositions, or reversals and all three kinds of transpositions, we have three problem models. After establishing a common lower bound on the number 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.