Publication Type:

Conference Paper

Source:

Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008) (2008)

URL:

http://ieeexplore.ieee.org/abstract/document/4439174/

Keywords:

Approximation algorithms, binary strings, bioinformatics, Computational complexity, Computational linguistics, Computer science, Frequency, Genome rearrangements, genomics, NP complete problem, Permutations, prefix transposition distance, Sorting, Upper Bound

Abstract:

A transposition is an operation that exchanges two adjacent substrings. When it is restricted so that one of the substrings is a prefix, it is called a prefix transposition. The prefix transposition distance between a pair of strings (permutations) is the shortest sequence of prefix transpositions required to transform a given string (permutation) into another given string (permutation). This problem is a variation of the transposition distance problem, related to genome rearrangements. An upper bound of n-1 and a lower bound of n/2 are known. We improve the bounds to n-log8 n and 2n/3 respectively. We also give upper and lower bounds for the prefix transposition distance on strings. For example, n/2 prefix transpositions are always sufficient for binary strings. We also prove that the exact prefix transposition distance problem on strings is NP complete.

Cite this Research Publication

Dr. Bhadrachalam Chitturi and Sudborough, I. H., “Bounding Prefix Transposition Distance for Strings and Permutations”, in Proceedings of the 41st Annual Hawaii International Conference on System Sciences (HICSS 2008), 2008.

207
PROGRAMS
OFFERED
6
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
8th
RANK(INDIA):
NIRF 2018
150+
INTERNATIONAL
PARTNERS