ABSTRACT
We discuss biologically motivated sorting algorithms, in which a permutation models a genome. The goal is to obtain the identity permutation using only a small set of allowed moves. These moves can be block transpositions, block interchanges, block reversals, or combinations or restricted versions of these. This are has many more open questions than answers, and some of the most intriguing ones concern an optimal sorting algorithm, finding the permutation that is the most difficult to sort, or finding the average number of steps needed to sort a permutation. For block interchange sorting, we present an exact answer to these questions.
