Article ID Journal Published Year Pages File Type
431119 Journal of Discrete Algorithms 2008 9 Pages PDF
Abstract

Genome rearrangement algorithms are powerful tools to analyze gene orders in molecular evolution. Analysis of genomes evolving by reversals and transpositions leads to a combinatorial problem of sorting by reversals and transpositions, the problem of finding a shortest sequence of reversals and transpositions that sorts one genome into the other. In this paper we present a 2k-approximation algorithm for sorting by reversals and transpositions for unsigned permutations where k is the approximation ratio of the algorithm used for cycle decomposition. For the best known value of k   our approximation ratio becomes 2.8386+δ2.8386+δ for any δ>0δ>0. We also derive a lower bound on reversal and transposition distance of an unsigned permutation.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,