Analysis of top-swap shuffling for genome rearrangements

DOI10.1214/105051607000000177zbMATH Open1135.92024arXivmath/0609171OpenAlexW3102151384MaRDI QIDQ2467609FDOQ2467609

Prasad Tetali, Nayantara Bhatnagar, Pietro Caputo, Eric Vigoda

Publication date: 28 January 2008

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Comparison theorems for reversible Markov chains
• Kinetically constrained spin models
• The equilibrium distribution for a generalized Sankoff-Ferretti model accurately predicts chromosome size distributions in a wide variety of species
• Relaxation time of \(L\)-reversal chains and other chromosome shuffles
• One-dimensional stepping stone models, sardine genetics and Brownian local time
• A remarkable nonlinear invariant for evolution with heterogeneous rates

Cited In (6)

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

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)