Bill Gates can’t spell ”von Neumann” !!! [p52 line 8]
I and Jimi Cullen read the Gates and Papadimitriou paper ”Bounds for Sorting by Prefix Reversal” (1979) that investigates how many flips [reversals of positions 1,2,..,k] of {1,2,3…,n} is needed to convert it into an arbitrary permutation and they found linear upper and lower bounds. Sometimes this is called the pan-cake flipping problem. They also investigate the same problem when the pancakes must end having the same side up, thus all experiencing an even number of flips.
This is a precursor to a paper by Hannenhalli and Pevzner (1995) that investigates the same problem where you can flip (invert) any interval in the permutation that also has a version where there are restrictions on the inversions on a given gene.
We were interested in this since we wondered if one could add swaps of neighbors to the TKF91 model since this would be of relevance in its applications to linguistics. This lead us to read Lowrance and Fischer (1974) that investigates the parsimony version of the problem and they only have a restricted solution when swaps can’t cross in the final alignment. We find this problem fun and will now try to look at a stochastic ”pure swap” problem and then maybe add insertion-deletions.
I should run this posting through Microsoft spelling checker to make sure I don’t have too many spelling errors myself, but I don’t trust it anymore.
HEIN RESEARCH 