Practical sampling of constraint-based models: Optimized thinning boosts CHRR performance

Thinning is a sub-sampling technique to reduce the memory footprint of Markov chain Monte Carlo. Despite being commonly used, thinning is rarely considered efficient. For sampling constraint-based models, a highly relevant use-case in systems biology, we here demonstrate that thinning boosts computational and, thereby, sampling efficiencies of the widely used Coordinate Hit-and-Run with Rounding (CHRR) algorithm. By benchmarking CHRR with thinning with simplices and genome-scale metabolic networks of up to thousands of dimensions, we find a substantial increase in computational efficiency compared to unthinned CHRR, in our examples by orders of magnitude, as measured by the effective sample size per time (ESS/t), with performance gains growing with polytope (effective network) dimension. Using a set of benchmark models we derive a ready-to-apply guideline for tuning thinning to efficient and effective use of compute resources without requiring additional coding effort. Our guideline is validated using three (out-of-sample) large-scale networks and we show that it allows sampling convex polytopes uniformly to convergence in a fraction of time, thereby unlocking the rigorous investigation of hitherto intractable models. The derivation of our guideline is explained in detail, allowing future researchers to update it as needed as new model classes and more training data becomes available. CHRR with deliberate utilization of thinning thereby paves the way to keep pace with progressing model sizes derived with the constraint-based reconstruction and analysis (COBRA) tool set. Sampling and evaluation pipelines are available at https://jugit.fz-juelich.de/IBG-1/ModSim/fluxomics/chrrt.Author summary: Analyzing the parameter spaces of genome-scale metabolic models (GEM) by means of Markov chain Monte Carlo (MCMC) sampling has become a key method in systems biology. In this context, sub-sampling, or thinning, reduces storage requirements and post-processing efforts of the immense sample volumes. However, sub-sampling is typically applied without due consideration, despite statisticians arguing that, by increasing the variance of the resulting estimate, thinning is almost always statistically inefficient. Considering synthetic and real sampling problems of widely varying complexity, we show that for the state-of-the-art uniform MCMC sampling algorithm, Coordinate Hit-and-Run with Rounding (CHRR), thinning has dramatic consequences on sampling performances: Our benchmarks reveal that sub-sampling boosts CHRR efficiencies, often by orders of magnitude, and the performance gain scales with problem dimension. For the studied problem classes, we provide simple rules of thumb for performance-optimized thinning, for which we give out-of-sample evidence. Utilization of our thinning guideline for GEMs, hence, keeps promise to solve hitherto inaccessible sampling problems, while for large scale networks its application can make the difference between immediate sampling success and repeated failures. In summary, on the one hand, optimized tuning of CHRR is now easily possible. On the other hand, thinning choice has to be registered when benchmarking CHRR implementations with regard to their running times.