Publication Type:

Journal Article


Theoretical Computer Science, Volume 421, p.15-24 (2012)



Approximation, Binary string, Bounds, Complexity, Computer science, Genome rearrangements, NP Complete, Prefix transpositions, Sub-strings, Upper and lower bounds, Upper Bound


A transposition is an operation that exchanges two adjacent substrings. Transpositions over permutations, the sequences with no repeated symbols, are related to genome rearrangements. If one of the substrings is restricted to a prefix then it is called a prefix transposition. The prefix transposition distance between a pair of strings (permutations) is the minimum number of prefix transpositions required to transform a given string (permutation) into another given string (permutation). For a permutation of length n, we improve the current prefix transposition distance upper bound of n-log 8n to n-log 92n. For arbitrary strings, we prove new prefix transposition distance upper and lower bounds. For binary strings of length n, we show that n2 is an upper bound. We show that the prefix transposition distance problem is NP-complete for binary strings. © 2011 Elsevier B.V. All rights reserved.


cited By (since 1996)2

Cite this Research Publication

Ba Chitturi and Sudborough, I. Hb, “Bounding prefix transposition distance for strings and permutations”, Theoretical Computer Science, vol. 421, pp. 15-24, 2012.