Publication Type:

Conference Proceedings


BIOCOMP 2009, p.562-566 (2009)



A k-bounded (k ≥ 2) transposition is an operation that switches two elements that have at most k - 2 elements in between. We study the problem of sorting a circular permutation π of length n for k = 2, i.e., adjacent swaps and k = 3, i.e., short swaps. These transpositions mimic microrearrangements of gene order in viruses and bacteria. We prove a (1/4)n (2) lower bound for sorting by adjacent swaps. We show upper bounds of (5/32)n (2) + O(n log n) and (7/8)n + O(log n) for sequential and parallel sorting, respectively, by short swaps.

Cite this Research Publication

X. Feng, Dr. Bhadrachalam Chitturi, and Liu, C., “Sorting Circular Permutations by Bounded Transpositions”, BIOCOMP 2009. pp. 562-566, 2009.