Qian-Ping Gu [1] (qian@u-aizu.ac.jp)
Shietung Peng [1] (s-peng@u-aizu.ac.jp)
Hal Sudborough [2] (hal@utdallas.edu)
[1] Department of Computer Software, The University of Aizu
Aizu-Wakamatsu, Fukushima, 965-80 Japan
[2] Department of Computer Science,
The University of Texas at Dallas Richardson, TX 75083 U.S.A.
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 two algorithms for the problem. Based on the lower bound, we show that the first algorithm is a 2-approximation algorithm. The time complexity of the algorithm may not be bounded by Poly(n), where n is the length of the permutation to be sorted. Setting a time limit to the first algorithm, we get the second algorithm which is a 2(1+1/k)-approximation one, where k > 3 is any fixed integer, and runs in Poly(n) time.