Approximation of sojourn-times via maximal couplings: motif frequency distributions

Autor: Manuel E. Lladser, Stephen R. Chestnut
Rok vydání: 2013
Předmět:
Zdroj: Journal of mathematical biology. 69(1)
ISSN: 1432-1416
Popis: Sojourn-times provide a versatile framework to assess the statistical significance of motifs in genome-wide searches even under non-Markovian background models. However, the large state spaces encountered in genomic sequence analyses make the exact calculation of sojourn-time distributions computationally intractable in long sequences. Here, we use coupling and analytic combinatoric techniques to approximate these distributions in the general setting of Polish state spaces, which encompass discrete state spaces. Our approximations are accompanied with explicit, easy to compute, error bounds for total variation distance. Broadly speaking, if $${\mathsf{T}}_n$$ is the random number of times a Markov chain visits a certain subset $${\mathsf{T}}$$ of states in its first $$n$$ transitions, then we can usually approximate the distribution of $${\mathsf{T}}_n$$ for $$n$$ of order $$(1-\alpha )^{-m}$$ , where $$m$$ is the largest integer for which the exact distribution of $${\mathsf{T}}_m$$ is accessible and $$0\le \alpha \le 1$$ is an ergodicity coefficient associated with the probability transition kernel of the chain. This gives access to approximations of sojourn-times in the intermediate regime where $$n$$ is perhaps too large for exact calculations, but too small to rely on Normal approximations or stationarity assumptions underlying Poisson and compound Poisson approximations. As proof of concept, we approximate the distribution of the number of matches with a motif in promoter regions of C. elegans. Mathematical properties of the proposed ergodicity coefficients and connections with additive functionals of homogeneous Markov chains as well as ergodicity of non-homogeneous Markov chains are also explored.
Databáze: OpenAIRE
Externí odkaz: