SORTING WITH FIXED-LENGTH REVERSALS

A popular puzzle TOP-SPIN consists of a permutation of 20 numbered dis ks on an oval track, with a tumstile capable of reversing a string of 4 consecutive disks. The goal is to sort the disks into identity permu tation using reversals. We consider the more general case of sorting n element permutations with a tumstile of size k. The problem of comput ing the reversal distances is of considerable importance in reconstruc ting the evolutionary history of the genome. The minimum reversal sequ ence sorting the one genome to another corresponds to the most likely evolutionary path between them. We give a complete solution for all n and k, of the number of equivalence classes of n-permutations under k- reversal, for both permutations and circular permutations. We also pro ve the upper and lower bounds on the reversal distances between two pe rmutations.