A 1.375-Approximation Algorithm for Sorting by Transpositions
2006 (English)In: IEEE/ACM Transactions on Computational Biology & Bioinformatics, ISSN 1545-5963, E-ISSN 1557-9964, Vol. 3, no 4, 369-379 p.Article in journal (Refereed) Published
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.
Place, publisher, year, edition, pages
2006. Vol. 3, no 4, 369-379 p.
computational biology, genome rearrangements, sorting permutations by transpositions
IdentifiersURN: urn:nbn:se:kth:diva-6354DOI: 10.1109/TCBB.2006.44ISI: 000241720700006ScopusID: 2-s2.0-33845654494OAI: oai:DiVA.org:kth-6354DiVA: diva2:11043
5th International Workshop on Algorithms in Bioinformatics (WABI 2005) Mallorca, Spain, OCT 03-06, 2005
QC 20110121 QC 20110927.2006-11-152006-11-152012-09-26Bibliographically approved