How Did We Get Here? Permutations as Genome Rearrange- ments

Here r ◦ p means the composition of the bijective functions r : [n] → [n] and p : [n] → [n], with r applied first. The left-invariant property described in (9.1) is explained by the fact that the distance between two genomes depends only on those two genomes, and not on the labeling of the genes in each genome. So relabeling the genes in one genome, and then relabeling the genes of the other genome in the same way will not change the distance between the two genomes. Setting r = q−1, formula (9.1) means that d(p, q) = d(q−1 ◦ p, id). So if

we know how to determine the distance of a generic permutation from the identity, then we also know how to find the distance of any two permutations from each other. This reduces our distance-measuring problem to a sorting problem. The

question we attempt to answer is now the following. Let us assume that the notion of distance is fixed. Given an arbitrary permutation p of length n, how many moves (of a specified kind) are necessary to transform p into the

of

increasing permutation 123 · · ·n? What is the permutation that is the most difficult to sort, that is, whose distance from the increasing permutation is the largest? How efficient is a given sorting method for the average permutation? Can we find an algorithm that finds the shortest distance from p to the increasing permutation?