CHRRT: boosting coordinate hit-and-run with rounding by thinning

bioRxiv (Cold Spring Harbor Laboratory)

Abstract

Abstract 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 convex polytopes uniformly, a highly relevant use-case in systems biology, we here demonstrate that thinning generally boosts computational and, thereby, sampling efficiencies of the widely used Coordinate Hit-and-Run with Rounding (CHRR) algorithm. We benchmark CHRR with thinning (CHRRT) with simplices and constrained-based metabolic networks with up to thousands of dimensions. With appropriate thinning, CHRRT offers a substantial increase in computational efficiency compared to unthinned CHRR, in our examples of up to three orders of magnitude, as measured by the effective sample size per time ( ESS/t ). Our experiments reveal that the performance gain of CHRRT by optimal thinning grows substantially with polytope (effective model) dimension. Based on our experiments, we provide practically useful advice for tuning thinning to efficient and effective use of compute resources. Besides allocating computational resources optimally to permit sampling convex polytopes uniformly to convergence in a fraction of time, exploiting thinning unlocks investigating hitherto intractable models under limited computational budgets. CHRRT thereby paves the way to keep pace with progressing model sizes within the existing 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 .

Authors 3

1. Johann F. Jadebeck Aachen Computational Systems Biotechnology

   RWTH Aachen University · Forschungszentrum Jülich

   Affiliation as printed

   Computational Systems Biotechnology (AVT.CSB), RWTH Aachen University, Aachen, Germany

   Institute of Bio- and Geosciences, IBG-1: Biotechnology, Forschungszentrum Jülich, Jülich, Germany

   Computational Systems Biotechnology (AVT.CSB), RWTH Aachen University

   Institute of Bio- and Geosciences, IBG-1: Biotechnology

2. Wolfgang Wiechert Aachen Computational Systems Biotechnology

   RWTH Aachen University · Forschungszentrum Jülich

   Affiliation as printed

   Computational Systems Biotechnology (AVT.CSB), RWTH Aachen University, Aachen, Germany

   Institute of Bio- and Geosciences, IBG-1: Biotechnology, Forschungszentrum Jülich, Jülich, Germany

   Computational Systems Biotechnology (AVT.CSB), RWTH Aachen University

   Institute of Bio- and Geosciences, IBG-1: Biotechnology

3. Katharina Nöh corresponding

   Forschungszentrum Jülich

   Affiliation as printed

   Institute of Bio- and Geosciences, IBG-1: Biotechnology, Forschungszentrum Jülich, Jülich, Germany

   Institute of Bio- and Geosciences, IBG-1: Biotechnology