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

作者：Lladser Manuel E^*; Chestnut Stephen R

来源：Journal of Mathematical Biology, 2014, 69(1): 147-182.

DOI：10.1007/s00285-013-0690-6

• Additive functionals of Markov chains
• Embedding technique
• Ergodicity coefficients
• Motifs
• Non-homogeneous Markov chains
• Non-asymptotic approximations of distributions
• Patterns
• Sojourn-times
• Wolfgang Doeblin

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 is the random number of times a Markov chain visits a certain subset of states in its first transitions, then we can usually approximate the distribution of for of order , where is the largest integer for which the exact distribution of is accessible and 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 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.

• 出版日期2014-7