Genome rearrangement: recent progress and open problems, preprint 2003

Genomes evolve by chromosomal fissions and fusions, reciprocal translocations between chro-mosomes, and inversions that change gene order within chromosomes. For more than a decade biologists and computer scientists have studied these processes by parsimony methods, i.e., what is the minimum number of events needed to turn one genome into another? We have recently begun to develop a stochastic approach to this and related questions, which has the advan-tage of producing confidence intervals for estimates and allowing tests of hypotheses concerning mechanisms. Our efforts are closely related to earlier work on card shuffling by Diaconis et al. However now we are not interested in how many shuffles are needed to obtain randomness, but instead want to look at the deck of cards and guess how many shuffles have been performed. This leads to interesting new questions and some surprising answers. This survey is a snapshot of work in progress. The bad news is that the treatment is far from definitive. The good news is that there are still a number of mysteries to solve. 1. Inversions. We begin with the simplest problem of the comparison of two chromosomes where the genetic material differs due to a number of inversions. This occurs for mitochondria