main page
A 1.375-Approximation Algorithm for Sorting
by Transpositions
Isaac Elias and Tzvika Hartman
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 ten-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 2-permutations and simple
permutations.
Download
-
-
In Proc. of the 5th International Workshop on Algorithms in Bioinformatics (WABI'05), volume 3692 of
Lecture Notes in Computer Science, pages 204-215. Springer-Verlag, October 2005.
(PDF, Springer)
-
Link to on-line computer aided proof
(HTML)
-
Slides from presentation given at Technion, Israel 2005
(PDF)
-
Google scholar citations Go Citeseer
BibTex
@InProceedings{WABI05:EliasHartman_SBT1375,
author = {Isaac Elias and Tzvika Hartman},
title = {A 1.375-Approximation Algorithm for Sorting by Transpositions},
booktitle = {Proc. of the 5th International Workshop on Algorithms in Bioinformatics ({WABI}'05)},
pages = {204--214},
year = {2005},
volume = {3692},
series = {Lecture Notes in Computer Science},
month = {October},
publisher = {Springer-Verlag},
ISBN = {3-540-29008-7},
}
|