Sorting circular permutations by bounded transpositions.
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.
Feng
Xuerong
X
Department of Biochemistry, University of Texas SW Medical Center, Dallas, TX 75390, USA.
Chitturi
Bhadrachalam
B
Sudborough
Hal
H
D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D003198:Computer Simulation; D019143:Evolution, Molecular; D023061:Gene Order; D015321:Gene Rearrangement; D006801:Humans; D008957:Models, Genetic