Publication Type:

Book Chapter


Advances in Computational Biology, Springer New York, New York, NY, p.725–736 (2010)





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 Sudborough, H., “Sorting Circular Permutations by Bounded Transpositions”, in Advances in Computational Biology, H. R. Arabnia, Ed. New York, NY: Springer New York, 2010, pp. 725–736.