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

Volume

3

Issue

4

fYear

2006

Firstpage

369

Lastpage

379

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;

fLanguage

English

Journal_Title

Computational Biology and Bioinformatics, IEEE/ACM Transactions on

Publisher

ieee

ISSN

1545-5963

Type

jour

DOI

10.1109/TCBB.2006.44

Filename

4015379