Relaxation time of L-reversal chains and other chromosome shuffles

DOI10.1214/105051606000000295MaRDI QIDQ862215zbMATH OpenOpenAlexFDO

Authors Fabio Martinelli, N. Cancrini, Pietro Caputo

Publication date 5 February 2007

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

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

Continuous-time Markov processes on discrete state spaces (60J27) Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20)

Abstract: We prove tight bounds on the relaxation time of the so-called

L

-reversal chain, which was introduced by R. Durrett as a stochastic model for the evolution of chromosome chains. The process is described as follows. We have

n

distinct letters on the vertices of the

n

-cycle (

m a t h b b Z

mod

n

); at each step, a connected subset of the graph is chosen uniformly at random among all those of length at most

L

, and the current permutation is shuffled by reversing the order of the letters over that subset. We show that the relaxation time

a u (n, L)

, defined as the inverse of the spectral gap of the associated Markov generator, satisfies

a u (n, L) = O (n v e e f r a c n^{3} L^{3})

. Our results can be interpreted as strong evidence for a conjecture of R. Durrett predicting a similar behavior for the mixing time of the chain.

Review text

R. Durrett has used an \(L\)-reversed continuous time Markov chain to model the evolution of chromosome chains. The state space consists of the \(n!\) configurations of an \(n\)-cycle with vertices numbered \(1\) to \(n\geq 2\) and the chain is obtained by doing \(L\)-reversals at the arrival times of a Poisson process with rate \(1\). A \(L\)-reversal consists in choosing a vertex at random (with uniform distribution) and independently choosing a length \(l\) (\(1\leq l\leq L\leq n\)) at random (with uniform distribution) and reversing the order of the vertices in the segment starting at \(x\) and ending at \(x+l\) (sum taken modulo \(n\)). Durrett has conjectured that the missing time \(T(n,L)=\inf \{t>0:\| p_{t}-\nu \| _{TV}\leq 1/e\}\) (where \(p_{t}\) and \(\nu \) are, respectively, the distribution at time \(t\) and the uniform distribution on the state space and \(TV\) stands for the total variation norm) satisfies \(\frac{1}{C}( \max (n,n^{3}/L^{3})) \log n\leq T(n,L)\leq C( \max (n,n^{3}/L^{3})) \log n\) for some constant \(C\). The upper bound was not proved and this paper could not prove or disprove it. Instead, it shows that \(\frac{1}{C}\max (n,n^{3}/L^{3})\leq \tau (n,L)\leq C( \max (n,n^{3}/L^{3})) \) for the relaxation time \(\tau (n,L)=\sup_{f} \text{Var}(f)/\mathcal{E}(f,f)\), where the supremum is taken over all non-constant functions \(f\) of the configuration \(\eta \), \(\text{Var}(f)=\frac{1}{n!}\sum_{\eta }f^{2}(\eta )-( \frac{1}{n!}\sum_{\eta }f(\eta )) ^{2}\) and \[ \mathcal{E}(f,f)=\frac{1}{2nL}\sum_{x=1}^{n}\sum_{l=1}^{L}\frac{1}{n!}\sum_{\eta }( (f(\eta ^{xl})-f(\eta )^{2}) \] with \(\eta ^{xl}\) the configuration resulting from \(\eta \) by doing the reversal described above. The authors also consider the case where the segment length is chosen according to a non-uniform distribution \(p(l)\propto \theta ^{l}\) and obtain \[ \frac{1}{C}\max (n,[ n(1-\theta )] ^{3})\leq \tau (n,\theta )\leq C( \max (n,[ n(1-\theta )] ^{3})) \] for \(\tau (n,\theta )=\sup_{f}\text{Var}(f)/\mathcal{E}_{\theta }(f,f)\) with \[ \mathcal{E}_{\theta }(f,f)=\frac{1-\theta }{2n}\sum_{x=1}^{n}\sum_{l=1}^{L}\theta ^{l-1}\frac{1}{n!}\sum_{\eta }( (f(\eta ^{xl})-f(\eta )^{2}). \]

Recommendations

Cites work

Cited in

(5)

This page was built for publication: Relaxation time of \(L\)-reversal chains and other chromosome shuffles

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