Pseudo-marginal approximation to the free energy in a micro-macro Markov chain Monte Carlo method

We introduce a generalized micro-macro Markov chain Monte Carlo (mM-MCMC) method with pseudo-marginal approximation to the free energy that is able to accelerate sampling of the microscopic Gibbs distributions when there is a time-scale separation between the macroscopic dynamics of a reaction coordinate and the remaining microscopic degrees of freedom. The mM-MCMC method attains this efficiency by iterating four steps: (i) propose a new value of the reaction coordinate, (ii) accept or reject the macroscopic sample, (iii) run a biased simulation that creates a microscopic molecular instance that lies close to the newly sampled macroscopic reaction coordinate value, and (iv) microscopic accept/reject step for the new microscopic sample. In the present paper, we eliminate the main computational bottleneck of earlier versions of this method: the necessity to have an accurate approximation of free energy. We show that the introduction of a pseudo-marginal approximation significantly reduces the computational cost of the microscopic accept/reject step while still providing unbiased samples. We illustrate the method's behavior on several molecular systems with low-dimensional reaction coordinates.

Optimal scaling of MCMC beyond Metropolis

The problem of optimally scaling the proposal distribution in a Markov chain Monte Carlo algorithm is critical to the quality of the generated samples. Much work has gone into obtaining such results for various Metropolis–Hastings (MH) algorithms. Recently, acceptance probabilities other than MH are being employed in problems with intractable target distributions. There are few resources available on tuning the Gaussian proposal distributions for this situation. We obtain optimal scaling results for a general class of acceptance functions, which includes Barker’s and lazy MH. In particular, optimal values for Barker’s algorithm are derived and found to be significantly different from that obtained for the MH algorithm. Our theoretical conclusions are supported by numerical simulations indicating that when the optimal proposal variance is unknown, tuning to the optimal acceptance probability remains an effective strategy.

Scalable and flexible inference framework for stochastic dynamic single-cell models

Understanding the inherited nature of how biological processes dynamically change over time and exhibit intra- and inter-individual variability, due to the different responses to environmental stimuli and when interacting with other processes, has been a major focus of systems biology. The rise of single-cell fluorescent microscopy has enabled the study of those phenomena. The analysis of single-cell data with mechanistic models offers an invaluable tool to describe dynamic cellular processes and to rationalise cell-to-cell variability within the population. However, extracting mechanistic information from single-cell data has proven difficult. This requires statistical methods to infer unknown model parameters from dynamic, multi-individual data accounting for heterogeneity caused by both intrinsic (e.g. variations in chemical reactions) and extrinsic (e.g. variability in protein concentrations) noise. Although several inference methods exist, the availability of efficient, general and accessible methods that facilitate modelling of single-cell data, remains lacking. Here we present a scalable and flexible framework for Bayesian inference in state-space mixed-effects single-cell models with stochastic dynamic. Our approach infers model parameters when intrinsic noise is modelled by either exact or approximate stochastic simulators, and when extrinsic noise is modelled by either time-varying, or time-constant parameters that vary between cells. We demonstrate the relevance of our approach by studying how cell-to-cell variation in carbon source utilisation affects heterogeneity in the budding yeast Saccharomyces cerevisiae SNF1 nutrient sensing pathway. We identify hexokinase activity as a source of extrinsic noise and deduce that sugar availability dictates cell-to-cell variability.

Computational Modeling of Glycan Processing in the Golgi for Investigating Changes in the Arrangements of Biosynthetic Enzymes

Modeling glycan biosynthesis is becoming increasingly important due to the far-reaching implications that glycosylation can exhibit, from pathologies to biopharmaceutical manufacturing. Here we describe a stochastic simulation approach, to overcome the deterministic nature of previous models, that aims to simulate the action of glycan modifying enzymes to produce a glycan profile. This is then coupled with an approximate Bayesian computation methodology to systematically fit to empirical data in order to determine which set of parameters adequately describes the organization of enzymes within the Golgi. The model is described in detail along with a proof of concept and therapeutic applications.

Direct statistical inference for finite Markov jump processes via the matrix exponential

Given noisy, partial observations of a time-homogeneous, finite-statespace Markov chain, conceptually simple, direct statistical inference is available, in theory, via its rate matrix, or infinitesimal generator, \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {Q}}$$\end{document}Q, since \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\exp ({\mathsf {Q}}t)$$\end{document}exp(Qt) is the transition matrix over time t. However, perhaps because of inadequate tools for matrix exponentiation in programming languages commonly used amongst statisticians or a belief that the necessary calculations are prohibitively expensive, statistical inference for continuous-time Markov chains with a large but finite state space is typically conducted via particle MCMC or other relatively complex inference schemes. When, as in many applications \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathsf {Q}}$$\end{document}Q arises from a reaction network, it is usually sparse. We describe variations on known algorithms which allow fast, robust and accurate evaluation of the product of a non-negative vector with the exponential of a large, sparse rate matrix. Our implementation uses relatively recently developed, efficient, linear algebra tools that take advantage of such sparsity. We demonstrate the straightforward statistical application of the key algorithm on a model for the mixing of two alleles in a population and on the Susceptible-Infectious-Removed epidemic model.

Influencing public health policy with data-informed mathematical models of infectious diseases: Recent developments and new challenges

Modern data and computational resources, coupled with algorithmic and theoretical advances to exploit these, allow disease dynamic models to be parameterised with increasing detail and accuracy. While this enhances models' usefulness in prediction and policy, major challenges remain. In particular, lack of identifiability of a model's parameters may limit the usefulness of the model. While lack of parameter identifiability may be resolved through incorporation into an inference procedure of prior knowledge, formulating such knowledge is often difficult. Furthermore, there are practical challenges associated with acquiring data of sufficient quantity and quality. Here, we discuss recent progress on these issues.

The effect of climate change on yellow fever disease burden in Africa

Yellow Fever (YF) is an arbovirus endemic in tropical regions of South America and Africa and it is estimated to cause 78,000 deaths a year in Africa alone. Climate change may have substantial effects on the transmission of YF and we present the first analysis of the potential impact on disease burden. We extend an existing model of YF transmission to account for rainfall and a temperature suitability index and project transmission intensity across the African endemic region in the context of four climate change scenarios. We use these transmission projections to assess the change in burden in 2050 and 2070. We find disease burden changes heterogeneously across the region. In the least severe scenario, we find a 93.0%[95%CI(92.7, 93.2%)] chance that annual deaths will increase in 2050. This change in epidemiology will complicate future control efforts. Thus, we may need to consider the effect of changing climatic variables on future intervention strategies.

Large-sample asymptotics of the pseudo-marginal method

The pseudo-marginal algorithm is a variant of the Metropolis–Hastings algorithm which samples asymptotically from a probability distribution when it is only possible to estimate unbiasedly an unnormalized version of its density. Practically, one has to trade off the computational resources used to obtain this estimator against the asymptotic variances of the ergodic averages obtained by the pseudo-marginal algorithm. Recent works on optimizing this trade-off rely on some strong assumptions, which can cast doubts over their practical relevance. In particular, they all assume that the distribution of the difference between the log-density, and its estimate is independent of the parameter value at which it is evaluated. Under regularity conditions we show that as the number of data points tends to infinity, a space-rescaled version of the pseudo-marginal chain converges weakly to another pseudo-marginal chain for which this assumption indeed holds. A study of this limiting chain allows us to provide parameter dimension-dependent guidelines on how to optimally scale a normal random walk proposal, and the number of Monte Carlo samples for the pseudo-marginal method in the large-sample regime. These findings complement and validate currently available results.

Modeling Glycan Processing Reveals Golgi-Enzyme Homeostasis upon Trafficking Defects and Cellular Differentiation

The decoration of proteins by carbohydrates is essential for eukaryotic life yet heterogeneous due to a lack of biosynthetic templates. This complex carbohydrate mixture—the glycan profile—is generated in the compartmentalized Golgi, in which level and localization of glycosylation enzymes are key determinants. Here, we develop and validate a computational model for glycan biosynthesis to probe how the biosynthetic machinery creates different glycan profiles. We combined stochastic modeling with Bayesian fitting that enables rigorous comparison to experimental data despite starting with uncertain initial parameters. This is an important development in the field of glycan modeling, which revealed biological insights about the glycosylation machinery in altered cellular states. We experimentally validated changes in N-linked glycan-modifying enzymes in cells with perturbed intra-Golgi-enzyme sorting and the predicted glycan-branching activity during osteogenesis. Our model can provide detailed information on altered biosynthetic paths, with potential for advancing treatments for glycosylation-related diseases and glyco-engineering of cells.

•

Developed a stochastic model of N-glycosylation coupled with Bayesian fitting

•

Validated predicted changes of Golgi organization in trafficking mutants

•

Model pinpointed functionally relevant glycan alterations in osteogenesis

On the use of approximate Bayesian computation Markov chain Monte Carlo with inflated tolerance and post-correction

Approximate Bayesian computation enables inference for complicated probabilistic models with intractable likelihoods using model simulations. The Markov chain Monte Carlo implementation of approximate Bayesian computation is often sensitive to the tolerance parameter: low tolerance leads to poor mixing and large tolerance entails excess bias. We propose an approach that involves using a relatively large tolerance for the Markov chain Monte Carlo sampler to ensure sufficient mixing and post-processing the output, leading to estimators for a range of finer tolerances. We introduce an approximate confidence interval for the related post-corrected estimators and propose an adaptive approximate Bayesian computation Markov chain Monte Carlo algorithm, which finds a balanced tolerance level automatically based on acceptance rate optimization. Our experiments show that post-processing-based estimators can perform better than direct Markov chain Monte Carlo targeting a fine tolerance, that our confidence intervals are reliable, and that our adaptive algorithm leads to reliable inference with little user specification.

HyperTraPS: Inferring Probabilistic Patterns of Trait Acquisition in Evolutionary and Disease Progression Pathways

The explosion of data throughout the biomedical sciences provides unprecedented opportunities to learn about the dynamics of evolution and disease progression, but harnessing these large and diverse datasets remains challenging. Here, we describe a highly generalizable statistical platform to infer the dynamic pathways by which many, potentially interacting, traits are acquired or lost over time. We use HyperTraPS (hypercubic transition path sampling) to efficiently learn progression pathways from cross-sectional, longitudinal, or phylogenetically linked data, readily distinguishing multiple competing pathways, and identifying the most parsimonious mechanisms underlying given observations. This Bayesian approach allows inclusion of prior knowledge, quantifies uncertainty in pathway structure, and allows predictions, such as which symptom a patient will acquire next. We provide visualization tools for intuitive assessment of multiple, variable pathways. We apply the method to ovarian cancer progression and the evolution of multidrug resistance in tuberculosis, demonstrating its power to reveal previously undetected dynamic pathways.

Statistical tools for seed bank detection

We derive statistical tools to analyze the patterns of genetic variability produced by models related to seed banks; in particular the Kingman coalescent, its time-changed counterpart describing so-called weak seed banks, the strong seed bank coalescent, and the two-island structured coalescent. As (strong) seed banks stratify a population, we expect them to produce a signal comparable to population structure. We present tractable formulas for Wright's F_ST and the expected site frequency spectrum for these models, and show that they can distinguish between some models for certain ranges of parameters. We then use pseudo-marginal MCMC to show that the full likelihood can reliably distinguish between all models in the presence of parameter uncertainty under moderate stratification, and point out statistical pitfalls arising from stratification that is either too strong or too weak. We further show that it is possible to infer parameters, and in particular determine whether mutation is taking place in the (strong) seed bank.

Unbiased approximations of products of expectations

We consider the problem of approximating the product of $n$ expectations with respect to a common probability distribution $\mu$. Such products routinely arise in statistics as values of the likelihood in latent variable models. Motivated by pseudo-marginal Markov chain Monte Carlo schemes, we focus on unbiased estimators of such products. The standard approach is to sample $N$ particles from $\mu$ and assign each particle to one of the expectations; this is wasteful and typically requires the number of particles to grow quadratically with the number of expectations. We propose an alternative estimator that approximates each expectation using most of the particles while preserving unbiasedness, which is computationally more efficient when the cost of simulations greatly exceeds the cost of likelihood evaluations. We carefully study the properties of our proposed estimator, showing that in latent variable contexts it needs only ${O} (n)$ particles to match the performance of the standard approach with ${O}(n^{2})$ particles. We demonstrate the procedure on two latent variable examples from approximate Bayesian computation and single-cell gene expression analysis, observing computational gains by factors of about 25 and 450, respectively.

Pseudo-marginal Metropolis–Hastings sampling using averages of unbiased estimators

We consider a pseudo-marginal Metropolis–Hastings kernel ${\mathbb{P}}_m$ that is constructed using an average of $m$ exchangeable random variables, and an analogous kernel ${\mathbb{P}}_s$ that averages $s<m$ of these same random variables. Using an embedding technique to facilitate comparisons, we provide a lower bound for the asymptotic variance of any ergodic average associated with ${\mathbb{P}}_m$ in terms of the asymptotic variance of the corresponding ergodic average associated with ${\mathbb{P}}_s$. We show that the bound is tight and disprove a conjecture that when the random variables to be averaged are independent, the asymptotic variance under ${\mathbb{P}}_m$ is never less than $s/m$ times the variance under ${\mathbb{P}}_s$. The conjecture does, however, hold for continuous-time Markov chains. These results imply that if the computational cost of the algorithm is proportional to $m$, it is often better to set $m=1$. We provide intuition as to why these findings differ so markedly from recent results for pseudo-marginal kernels employing particle filter approximations. Our results are exemplified through two simulation studies; in the first the computational cost is effectively proportional to $m$ and in the second there is a considerable start-up cost at each iteration.

Particle MCMC algorithms and architectures for accelerating inference in state-space models

•

Novel algorithmic and hardware techniques for fast SSM inference are proposed.

•

New algorithm extends applicability of particle MCMC to multi-modal posteriors.

•

FPGA architectures exploit particle and chain parallelism to accelerate sampling.

•

42x speedup vs. state-of-the-art CPU/GPU samplers is achieved for large problems.

Particle Markov Chain Monte Carlo (pMCMC) is a stochastic algorithm designed to generate samples from a probability distribution, when the density of the distribution does not admit a closed form expression. pMCMC is most commonly used to sample from the Bayesian posterior distribution in State-Space Models (SSMs), a class of probabilistic models used in numerous scientific applications. Nevertheless, this task is prohibitive when dealing with complex SSMs with massive data, due to the high computational cost of pMCMC and its poor performance when the posterior exhibits multi-modality. This paper aims to address both issues by: 1) Proposing a novel pMCMC algorithm (denoted ppMCMC), which uses multiple Markov chains (instead of the one used by pMCMC) to improve sampling efficiency for multi-modal posteriors, 2) Introducing custom, parallel hardware architectures, which are tailored for pMCMC and ppMCMC. The architectures are implemented on Field Programmable Gate Arrays (FPGAs), a type of hardware accelerator with massive parallelization capabilities. The new algorithm and the two FPGA architectures are evaluated using a large-scale case study from genetics. Results indicate that ppMCMC achieves 1.96x higher sampling efficiency than pMCMC when using sequential CPU implementations. The FPGA architecture of pMCMC is 12.1x and 10.1x faster than state-of-the-art, parallel CPU and GPU implementations of pMCMC and up to 53x more energy efficient; the FPGA architecture of ppMCMC increases these speedups to 34.9x and 41.8x respectively and is 173x more power efficient, bringing previously intractable SSM-based data analyses within reach.

Bayesian inference for age-structured population model of infectious disease with application to varicella in Poland

The dynamics of the infectious disease transmission are often best understood by taking into account the structure of population with respect to specific features, for example age or immunity level. The practical utility of such models depends on the appropriate calibration with the observed data. Here, we discuss the Bayesian approach to data assimilation in the case of a two-state age-structured model. Such models are frequently used to explore the disease dynamics (i.e. force of infection) based on prevalence data collected at several time points. We demonstrate that, in the case when the explicit solution to the model equation is known, accounting for the data collection process in the Bayesian framework allows us to obtain an unbiased posterior distribution for the parameters determining the force of infection. We further show analytically and through numerical tests that the posterior distribution of these parameters is stable with respect to a cohort approximation (Escalator Boxcar Train) of the solution. Finally, we apply the technique to calibrate the model based on observed sero-prevalence of varicella in Poland.

State-space reduction and equivalence class sampling for a molecular self-assembly model

Direct simulation of a model with a large state space will generate enormous volumes of data, much of which is not relevant to the questions under study. In this paper, we consider a molecular self-assembly model as a typical example of a large state-space model, and present a method for selectively retrieving 'target information' from this model. This method partitions the state space into equivalence classes, as identified by an appropriate equivalence relation. The set of equivalence classes H, which serves as a reduced state space, contains none of the superfluous information of the original model. After construction and characterization of a Markov chain with state space H, the target information is efficiently retrieved via Markov chain Monte Carlo sampling. This approach represents a new breed of simulation techniques which are highly optimized for studying molecular self-assembly and, moreover, serves as a valuable guideline for analysis of other large state-space models.

Unbiased Bayesian inference for population Markov jump processes via random truncations

We consider continuous time Markovian processes where populations of individual agents interact stochastically according to kinetic rules. Despite the increasing prominence of such models in fields ranging from biology to smart cities, Bayesian inference for such systems remains challenging, as these are continuous time, discrete state systems with potentially infinite state-space. Here we propose a novel efficient algorithm for joint state/parameter posterior sampling in population Markov Jump processes. We introduce a class of pseudo-marginal sampling algorithms based on a random truncation method which enables a principled treatment of infinite state spaces. Extensive evaluation on a number of benchmark models shows that this approach achieves considerable savings compared to state of the art methods, retaining accuracy and fast convergence. We also present results on a synthetic biology data set showing the potential for practical usefulness of our work.

Stability of noisy Metropolis-Hastings

Pseudo-marginal Markov chain Monte Carlo methods for sampling from intractable distributions have gained recent interest and have been theoretically studied in considerable depth. Their main appeal is that they are exact, in the sense that they target marginally the correct invariant distribution. However, the pseudo-marginal Markov chain can exhibit poor mixing and slow convergence towards its target. As an alternative, a subtly different Markov chain can be simulated, where better mixing is possible but the exactness property is sacrificed. This is the noisy algorithm, initially conceptualised as Monte Carlo within Metropolis, which has also been studied but to a lesser extent. The present article provides a further characterisation of the noisy algorithm, with a focus on fundamental stability properties like positive recurrence and geometric ergodicity. Sufficient conditions for inheriting geometric ergodicity from a standard Metropolis-Hastings chain are given, as well as convergence of the invariant distribution towards the true target distribution.