abcdefg -> abedcfg (a reversal)and
abcdefg -> adebcfg (a transposition)are simple substring-rearrangement operations that can model large-scale genetic change mechanisms. Given two strings containing the same characters, it is natural to ask the smallest number of reversals (or transpositions) necessary to change one into the other. The geometry of these distances, and the complexity of determining them, have been extensively investigated for permutations. We consider these questions for strings over finite alphabets, finding many parallels but also some significant differences.
This work is joint with Jamie Radcliffe and Alex Scott.