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 Dt be the minimum number of transpositions needed to go back to the identity element from the location at time t. Dt undergoes a phase transition: for 0 < c ≤ 1, the distance Dcn/2 ~ cn/2, i.e., the distance increases linearly with time; for c > 1, Dcn/2 ~ u(c)n where u is an explicit function satisfying u(x)