Analysis of top-swap shuffling for genome rearrangements

Simple item page
dc.creatorBhatnagar, Nayantara
dc.creatorCaputo, Pietro
dc.creatorTetali, Prasad
dc.creatorVigoda, Eric
dc.date2006-09-06
dc.date2007-10-24
dc.date.accessioned2026-07-07T08:38:30Z
dc.date.available2026-07-07T08:38:30Z
dc.descriptionWe study Markov chains which model genome rearrangements. These models are useful for studying the equilibrium distribution of chromosomal lengths, and are used in methods for estimating genomic distances. The primary Markov chain studied in this paper is the top-swap Markov chain. The top-swap chain is a card-shuffling process with $n$ cards divided over $k$ decks, where the cards are ordered within each deck. A transition consists of choosing a random pair of cards, and if the cards lie in different decks, we cut each deck at the chosen card and exchange the tops of the two decks. We prove precise bounds on the relaxation time (inverse spectral gap) of the top-swap chain. In particular, we prove the relaxation time is $Θ(n+k)$. This resolves an open question of Durrett.
dc.descriptionPublished in at http://dx.doi.org/10.1214/105051607000000177 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
dc.identifierhttps://arxiv.org/abs/math/0609171
dc.identifierhttp://arxiv.org/abs/math/0609171
dc.identifierAnnals of Applied Probability 2007, Vol. 17, No. 4, 1424-1445
dc.identifierdoi:10.1214/105051607000000177
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/140753
dc.subjectProbability
dc.subject60J27 (Primary) 92D10 (Secondary)
dc.titleAnalysis of top-swap shuffling for genome rearrangements
dc.typetext

Files

Collections

arXiv