Title :
A 1.375-Approximation Algorithm for Sorting by Transpositions
Author :
Elias, Isaac ; Hartman, Tzvika
Author_Institution :
Dept. of Numerical Anal. & comput. Sci., R. Inst. of Technol., Stockholm
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
Keywords :
approximation theory; biology computing; genetics; molecular biophysics; approximation algorithm; complexity; genome rearrangements; permutations; sorting; symmetric group; transposition diameter; Approximation algorithms; Bioinformatics; Evolution (biology); Genetic mutations; Genomics; Organisms; Robustness; Sequences; Sorting; Upper bound; Computational biology; genome rearrangements; sorting permutations by transpositions.; Algorithms; Chromosome Mapping; DNA Mutational Analysis; DNA Transposable Elements; Evolution, Molecular; Linkage Disequilibrium; Sequence Analysis, DNA;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2006.44
