Change search
ReferencesLink to record
Permanent link

Direct link
A 1.375-approximation algorithm for sorting by transpositions
KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.
2005 (English)In: ALLGORITHMS IN BIONIFORMATICS, PROCEEDINGS / [ed] Casadio, R; Myers, G, BERLIN: SPRINGER-VERLAG BERLIN , 2005, Vol. 3692, 204-215 p.Conference paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
BERLIN: SPRINGER-VERLAG BERLIN , 2005. Vol. 3692, 204-215 p.
National Category
Computer Science
URN: urn:nbn:se:kth:diva-42698DOI: 10.1007/11557067_17ISI: 000233555100017ScopusID: 2-s2.0-30544441155ISBN: 3-540-29008-7OAI: diva2:447437
5th International Workshop on Algorithms in Bioinformatics. Mallorca, SPAIN. OCT 03-06, 2005
QC 20111011Available from: 2011-10-12 Created: 2011-10-11 Last updated: 2011-10-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Elias, Isaac
By organisation
Numerical Analysis and Computer Science, NADA
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 19 hits
ReferencesLink to record
Permanent link

Direct link