A 2-APPROXIMATION ALGORITHM FOR GENOME REARRANGEMENTS BY REVERSALS AND TRANSPOSITIONS

Recently, a new approach to analyze genomes evolving which is based on comparision of gene orders versus traditional comparision of DNA sequ ences was proposed (Sankoff et al. 1992). The approach is based on the global rearrangements (e.g., inversions and transpositions of fragmen ts). Analysis of genomes evolving by inversions and transpositions lea ds to a combinatorial problem of sorting by reversals and transpositio ns, i.e., sorting of a permutation using reversals and transpositions of arbitrary fragments. We study sorting of signed permutations by rev ersals and transpositions, a problem which adequately models genome re arrangements, as the genes in DNA are oriented. We establish a lower b ound and give a 2-approximation algorithm for the problem. (C) 1999-El sevier Science B.V. All rights reserved.