A 1.375-approximation algorithm for sorting by transpositions

IEEE/ACM Trans Comput Biol Bioinform. 2006 Oct-Dec;3(4):369-79. doi: 10.1109/TCBB.2006.44.

Abstract

Sorting permutations by transpositions is an important problem in genome rearrangements. A transposition is a rearrangement operation in which a segment is cut out of the permutation and pasted in a different location. The complexity of this problem is still open and it has been a 10-year-old open problem to improve the best known 1.5-approximation algorithm. In this paper, we provide a 1.375-approximation algorithm for sorting by transpositions. The algorithm is based on a new upper bound on the diameter of 3-permutations. In addition, we present some new results regarding the transposition diameter: we improve the lower bound for the transposition diameter of the symmetric group and determine the exact transposition diameter of simple permutations.

MeSH terms

  • Algorithms*
  • Chromosome Mapping / methods*
  • DNA Mutational Analysis / methods*
  • DNA Transposable Elements / genetics*
  • Evolution, Molecular*
  • Linkage Disequilibrium / genetics*
  • Sequence Analysis, DNA / methods*

Substances

  • DNA Transposable Elements