A 1.375-approximation algorithm for sorting by transpositions
1Department of Numerical Analysis and Computer Science, Royal Institute of Technology, Stockholm, Sweden. isaac@nada.kth.se
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.
More Related Videos
Related Concept Videos
Overview of Transposition and Recombination
Transposons
Partial Fractions
Kendall's Tau Test
A τ value of +1 indicates that...
Translocation of Proteins into the Mitochondria
Sorting of outer membrane proteins:
Mitochondrial outer membrane proteins are of two types: the transmembrane, beta-barrel porins, and the membrane-anchored, alpha-helical proteins. Beta-barrel porin precursors are translocated by the TOM complex and inserted into the outer mitochondrial membrane by the SAM complex. In contrast,...
Disubstituted Cyclohexanes: cis-trans Isomerism
In cyclohexane, the substituents can occupy different positions generating distinct isomers.


