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