  Our work is motivated by Bourque and Pevzner's (2002) simulation study of the
effectiveness of the parsimony method in studying genome rearrangement, and
leads to a surprising result about the random transposition walk on the group
of permutations on $n$ elements. Consider this walk in continuous time starting
at the identity and let $D_t$ be the minimum number of transpositions needed to
go back to the identity from the location at time $t$. $D_t$ undergoes a phase
transition: the distance $D_{cn/2} \sim u(c)n$, where $u$ is an explicit
function satisfying $u(c)=c/2$ for $c \le 1$ and $u(c)1$. In other words, the
distance to the identity is roughly linear during the subcritical phase, and
after critical time $n/2$ it becomes sublinear. In addition, we describe the
fluctuations of $D_{cn/2}$ about its mean in each of the threeregimes
(subcritical, critical and supercritical). The techniques used involve viewing
the cycles in the random permutation as a coagulation-fragmentation process and
relating the behavior to the \Erd\H{o}s-Renyi random graph model.
