2013/02/01 by Dawn B. Woodard, Jeffrey S. Rosenthal
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Artificial intelligence #Bayesian Methods and Mixture Models #Bayesian probability #Biology #Computer science #Convergence (economics) #Ergodicity #False discovery rate #Gene #Genetic and phenotypic traits in livestock #Genetics #Genomics and Chromatin Dynamics #Gibbs sampling #Hidden Markov model #Markov chain #Markov chain Monte Carlo #Mathematics #Monte Carlo method #Posterior probability #Rate of convergence #Statistics #math.ST #stat.TH
paper · pdf · doi:10.1214/12-aos1075
published as Annals of Statistics 2013, Vol. 41, No. 1, 91-124 · Published in at http://dx.doi.org/10.1214/12-AOS1075 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
openalex publication_date 2013/02/01 · arxiv created 2013/03/12 · arxiv updated 2013/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We analyze the convergence rate of a simplified version of a popular Gibbs sampling method used for statistical discovery of gene regulatory binding motifs in DNA sequences. This sampler satisfies a very strong form of ergodicity (uniform). However, we show that, due to multimodality of the posterior distribution, the rate of convergence often decreases exponentially as a function of the length of the DNA sequence. Specifically, we show that this occurs whenever there is more than one true repeating pattern in the data. In practice there are typically multiple such patterns in biological data, the goal being to detect the most well-conserved and frequently-occurring of these. Our findings match empirical results, in which the motif-discovery Gibbs sampler has exhibited such poor convergence that it is used only for finding modes of the posterior distribution (candidate motifs) rather than for obtaining samples from that distribution. Ours are some of the first meaningful bounds on the convergence rate of a Markov chain method for sampling from a multimodal posterior distribution, as a function of statistical quantities like the number of observations.