Analysis of top-swap shuffling for genome rearrangements

DOI10.1214/105051607000000177MaRDI QIDQ2467609zbMATH OpenOpenAlexFDO

Authors Nayantara Bhatnagar, Prasad Tetali, Eric Vigoda, Pietro Caputo

Publication date 28 January 2008

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609171

zbMATH Keywords

Markov processrelaxation timespectral gapreciprocal translocation

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Continuous-time Markov processes on discrete state spaces (60J27)

Abstract: 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.

Recommendations

• Relaxation time of \(L\)-reversal chains and other chromosome shuffles
• Shuffling chromosomes
• Analysis of top to bottom-\(k\) shuffles

Cites work

• scientific article; zbMATH DE number 1306890 (Why is no real title available?)
• A remarkable nonlinear invariant for evolution with heterogeneous rates
• Comparison theorems for reversible Markov chains
• Distance-based genome rearrangement phylogeny
• Kinetically constrained spin models
• One-dimensional stepping stone models, sardine genetics and Brownian local time
• Relaxation time of \(L\)-reversal chains and other chromosome shuffles
• The equilibrium distribution for a generalized Sankoff-Ferretti model accurately predicts chromosome size distributions in a wide variety of species

Cited in

(8)

• Generating a random signed permutation with random reversals
• Mixing time and local exponential ergodicity of the east-like process in \(\mathbb{Z}^d\)
• Shuffling chromosomes
• Bisection for kinetically constrained models revisited
• Relaxation time of \(L\)-reversal chains and other chromosome shuffles
• Spectral gap for stochastic energy exchange model with nonuniformly positive rate function
• Relaxation to equilibrium of generalized east processes on \(\mathbb{Z}^{d}\): renormalization group analysis and energy-entropy competition
• Time scale separation and dynamic heterogeneity in the low temperature East model

This page was built for publication: Analysis of top-swap shuffling for genome rearrangements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2467609)