INTERDISCIPLINARY STOCHASTIC PROCESSES COLLOQUIUM

Thursday February 12, room 330 Evans, 3.10 - 4.00pm

Speaker: Rick Durrett (Cornell)

Title: A Phase Transition in Genome Rearrangement


Abstract:
Motivated by simulation results of Bourque-Pevzner (2002)
on effectiveness of parsimony method in genome rearrangement,
we study the random transposition walk on $n$-permutations. 
Consider the minimum number $D_t$ of transpositions needed
to return to the identity from the time-$t$ distribution.
Then $D_t$ has a phase transition, in the sense that
$D_{cn/2}$ behaves as $u(c) n$ for a certain explicit $u(c)$.
The techniques used involve viewing the cycles in the random
transposition as a coagulation-fragmentation processes and
relating to the behavior in the Erdos-Renyi random graph model.