Analysis of top-swap shuffling for genome rearrangements

Mathematics – Probability

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Published in at http://dx.doi.org/10.1214/105051607000000177 the Annals of Applied Probability (http://www.imstat.org/aap/) by

Scientific paper

10.1214/105051607000000177

We 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 $\Theta(n+k)$. This resolves an open question of Durrett.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Analysis of top-swap shuffling for genome rearrangements does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Analysis of top-swap shuffling for genome rearrangements, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of top-swap shuffling for genome rearrangements will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-418903

All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.