Nathanael Berestycki
Cornell University
Title: Phase transition and Geometry of random transpositions

We are originally motivated by a problem in genome rearrangement. One way to formulate this problem is to ask what is the rate of evolution induced by certain large-scale mutations called inversions. If we think of a chromosome as being made up of n markers (the genes), a reversal is a mutation that chooses a segment of the chromosome and flips it around to reverse its order. Traditionally, biologists have studied these questions with parsimony methods. However, it was observed numerically by Hannehalli and Pevzner that this method provides accurate results only if the number of mutations is small enough. Our work provides a theoretical explanation for this fact and allows to consider the case of many mutations. We consider the mathematically cleaner but similar problem of random transpositions. Let sigma(t) be the composition of random uniform transpositions performed at rate 1. sigma(t) can be viewed as a random walk on some Cayley graph of the symmetric group. If D(t) is the distance between sigma(t) and its starting point, we prove that D(t) undergoes a phase transition at critical time n/2, from a linear to a sublinear behavior. We will also describe the consequences of this result for the geometry of the graph, which involves a connection with Gromov hyperbolic spaces.
©2004, Department of Mathematical Sciences
Last Modified: November 10, 2004