A New Approximation Algorithm for Sorting of Signed Permutations

Sequence comparison leads to a combinatorial optimization problem of sortingpermutations by reversals and transpositions. Namely, given any two permutations, nd the short-est distance between them. This problem is related with genome rearrangement. The sorting of signed permutations is studied. Because in genome rearrangement, genes are oriented in DNA se-quences. The transpositions which have been studied in the literature can be viewed as operations working on two consecutive segments of the genome. In this paper, a new kind of transposition which can work on two arbitrary segments of the genome is proposed, and the sorting of signed permutations by reversals and this new kind of transpositions are studied. After establishing a lower bound on the number of operations needed, a 2-approximation algorithm is presented for this problem and an example is given to show that the performance ratio of the algorithm cannot be improved.