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 processreciprocal translocationrelaxation timespectral gap

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) Continuous-time Markov processes on discrete state spaces (60J27) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10)

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.

Review text

A top-swap Markov chain is described which can be considered as a card-shuffling process. It is used to model reciprocal translocations between chromosomes. The model has two parameters: the number of genes (cards) \(n\) and the number of chromosomes (decks) \(k\). The cards are ordered in each deck. At each transition two random positions are chosen at decks and if they are in different decks the tops of these decks are exchanged. If the positions are at the same deck there are two variants: to do nothing or to invert the order of cards between these positions. (The last variant is used to describe genes inversion). Let \(\tau(n,k)\) be the relaxation time (the inverse of the spectral gap) of the top-swap chain. It is shown that \(\exists\;C_1>C_2>0\) such that \[ C_1(n+k)\leq \tau(n,k)\leq C_2(n+k). \] Some generalizations are also considered.

Recommendations

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

Cites work

• A remarkable nonlinear invariant for evolution with heterogeneous rates
• Comparison theorems for reversible Markov chains
• Distance-based genome rearrangement phylogeny
• scientific article; zbMATH DE number 1306890 (Why is no real title available?)
• 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)

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

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)