Our work is motivated by Bourque-Pevzner's simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk in continuous time on the group of permutations on n elements starting from the identity. Let be the minimum number of transpositions needed to go back to the identity element from the location at time . undergoes a phase transition: for , the distance , i.e., the distance increases linearly with time; for , where is an explicit function satisfying . Moreover we describe the fluctuations of about its mean at each of the three stages (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ős-Rényi random graph model.