A 1.375-approximation algorithm for sorting by transpositions.
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.
Elias
Isaac
I
Department of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, Sweden. isaac@nada.kth.se
Hartman
Tzvika
T
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D004252:DNA Mutational Analysis / Q000379:methods*; D004251:DNA Transposable Elements / Q000235:genetics*; D019143:Evolution, Molecular; D015810:Linkage Disequilibrium / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*
D004251:DNA Transposable Elements