{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T00:38:52Z","timestamp":1771461532490,"version":"3.50.1"},"reference-count":38,"publisher":"Oxford University Press (OUP)","issue":"15","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: Random sampling of the solution space has emerged as a popular tool to explore and infer properties of large metabolic networks. However, conventional sampling approaches commonly used do not eliminate thermodynamically unfeasible loops.<\/jats:p><jats:p>Results: In order to overcome this limitation, we developed an efficient sampling algorithm called loopless Artificially Centered Hit-and-Run on a Box (ll-ACHRB). This algorithm is inspired by the Hit-and-Run on a Box algorithm for uniform sampling from general regions, but employs the directions of choice approach of Artificially Centered Hit-and-Run. A novel strategy for generating feasible warmup points improved both sampling efficiency and mixing. ll-ACHRB shows overall better performance than current strategies to generate feasible flux samples across several models. Furthermore, we demonstrate that a failure to eliminate unfeasible loops greatly affects sample statistics, in particular the correlation structure. Finally, we discuss recommendations for the interpretation of sampling results and possible algorithmic improvements.<\/jats:p><jats:p>Availability and implementation: Source code for MATLAB and OCTAVE including examples are freely available for download at http:\/\/www.aibn.uq.edu.au\/cssb-resources under Software. Optimization runs can use Gurobi Optimizer (by default if available) or GLPK (included with the algorithm).<\/jats:p><jats:p>Contact: \u00a0lars.nielsen@uq.edu.au<\/jats:p><jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw132","type":"journal-article","created":{"date-parts":[[2016,3,13]],"date-time":"2016-03-13T01:18:47Z","timestamp":1457831927000},"page":"2330-2337","source":"Crossref","is-referenced-by-count":36,"title":["ll-ACHRB: a scalable algorithm for sampling the feasible solution space of metabolic networks"],"prefix":"10.1093","volume":"32","author":[{"given":"Pedro A.","family":"Saa","sequence":"first","affiliation":[{"name":"Australian Institute for Bioengineering and Nanotechnology (AIBN), The University of Queensland, St Lucia, QLD, Australia"}]},{"given":"Lars K.","family":"Nielsen","sequence":"additional","affiliation":[{"name":"Australian Institute for Bioengineering and Nanotechnology (AIBN), The University of Queensland, St Lucia, QLD, Australia"}]}],"member":"286","published-online":{"date-parts":[[2016,3,11]]},"reference":[{"key":"2023020112472048400_btw132-B1","doi-asserted-by":"crossref","first-page":"839","DOI":"10.1038\/nature02289","article-title":"Global organization of metabolic fluxes in the bacterium Escherichia coli","volume":"427","author":"Almaas","year":"2004","journal-title":"Nature"},{"key":"2023020112472048400_btw132-B2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0006-3495(02)75150-3","article-title":"Energy balance for analysis of complex metabolic networks","volume":"83","author":"Beard","year":"2002","journal-title":"Biophys. J"},{"key":"2023020112472048400_btw132-B3","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1038\/msb.2010.68","article-title":"Insight into human alveolar macrophage and M. tuberculosis interactions via metabolic reconstructions","volume":"6","author":"Bordbar","year":"2010","journal-title":"Molecular systems biology"},{"key":"2023020112472048400_btw132-B4","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1186\/1752-0509-5-110","article-title":"iAB-RBC-283: a proteomically derived knowledge-base of erythrocyte metabolism that can be used to simulate its physiological and patho-physiological states","volume":"5","author":"Bordbar","year":"2011","journal-title":"BMC Syst. Biol"},{"key":"2023020112472048400_btw132-B5","doi-asserted-by":"crossref","first-page":"737","DOI":"10.15252\/msb.20145243","article-title":"Minimal metabolic pathway structure is consistent with associated biomolecular interactions","volume":"10","author":"Bordbar","year":"2014","journal-title":"Mol. Syst. Biol"},{"key":"2023020112472048400_btw132-B6","doi-asserted-by":"crossref","first-page":"e1000859","DOI":"10.1371\/journal.pcbi.1000859","article-title":"Sampling the solution space in genome-scale metabolic networks reveals transcriptional regulation in key enzymes","volume":"6","author":"Bordel","year":"2010","journal-title":"PLOS Comput. Biol"},{"key":"2023020112472048400_btw132-B7","first-page":"4","article-title":"A multi-tissue genome-scale metabolic modeling framework for the analysis of whole plant systems","volume":"6","author":"Dal'Molin","year":"2015","journal-title":"Front. Plant Sci"},{"key":"2023020112472048400_btw132-B8","doi-asserted-by":"crossref","first-page":"e0122670","DOI":"10.1371\/journal.pone.0122670","article-title":"Uniform sampling of steady states in metabolic networks: heterogeneous scales and rounding","volume":"10","author":"De Martino","year":"2015","journal-title":"Plos One"},{"key":"2023020112472048400_btw132-B9","doi-asserted-by":"crossref","first-page":"967","DOI":"10.1137\/0217060","article-title":"On the complexity of computing the volume of a polyhedron","volume":"17","author":"Dyer","year":"1988","journal-title":"SIAM J. Comput"},{"key":"2023020112472048400_btw132-B10","doi-asserted-by":"crossref","first-page":"e1003575","DOI":"10.1371\/journal.pcbi.1003575","article-title":"Constraint-based modeling of carbon fixation and the energetics of electron transfer in geobacter metallireducens","volume":"10","author":"Feist","year":"2014","journal-title":"PLOS Comput. Biol"},{"key":"2023020112472048400_btw132-B11","doi-asserted-by":"crossref","DOI":"10.1002\/9781118555552","volume-title":"Computational Statistics","author":"Givens","year":"2012"},{"key":"2023020112472048400_btw132-B12","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1080\/00031305.1998.10480547","article-title":"Markov Chain Monte Carlo in Practice: a roundtable discussion","volume":"52","author":"Kass","year":"1998","journal-title":"Am. Stat"},{"key":"2023020112472048400_btw132-B13","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1287\/opre.46.1.84","article-title":"Direction choice for accelerated convergence in hit-and-run sampling","volume":"46","author":"Kaufman","year":"1998","journal-title":"Oper. Res"},{"key":"2023020112472048400_btw132-B14","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1921598.1921600","article-title":"An analysis of a variation of hit-and-run for uniform sampling from general regions","volume":"21","author":"Kiatsupaibul","year":"2011","journal-title":"ACM Trans. Model. Comput. Simul"},{"key":"2023020112472048400_btw132-B15","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1038\/nrmicro2737","article-title":"Constraining the metabolic genotype-phenotype relationship using a phylogeny of in silico methods","volume":"10","author":"Lewis","year":"2012","journal-title":"Nat. Rev. Microbiol"},{"key":"2023020112472048400_btw132-B16","doi-asserted-by":"crossref","first-page":"1279","DOI":"10.1038\/nbt.1711","article-title":"Large-scale in silico modeling of metabolic interactions between cell types in the human brain","volume":"28","author":"Lewis","year":"2010","journal-title":"Nat. Biotechnol"},{"key":"2023020112472048400_btw132-B17","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s101070050099","article-title":"Hit-and-run mixes fast","volume":"86","author":"Lovasz","year":"1999","journal-title":"Math. Prog"},{"key":"2023020112472048400_btw132-B18","doi-asserted-by":"crossref","first-page":"e86587","DOI":"10.1371\/journal.pone.0086587","article-title":"optGpSampler: an improved tool for uniformly sampling the solution-space of genome-scale metabolic networks","volume":"9","author":"Megchelenbrink","year":"2014","journal-title":"Plos One"},{"key":"2023020112472048400_btw132-B19","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1186\/1752-0509-3-37","article-title":"Connecting extracellular metabolomic measurements to intracellular flux states in yeast","volume":"3","author":"Mo","year":"2009","journal-title":"BMC Syst. Biol"},{"key":"2023020112472048400_btw132-B20","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1214\/aos\/1056562461","article-title":"Slice sampling","volume":"31","author":"Neal","year":"2003","journal-title":"Ann. Stat"},{"key":"2023020112472048400_btw132-B21","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.compbiomed.2006.01.002","article-title":"Algorithm for perturbing thermodynamically infeasible metabolic networks","volume":"37","author":"Nigam","year":"2007","journal-title":"Comput. Biol. Med"},{"key":"2023020112472048400_btw132-B22","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1038\/msb.2011.65","article-title":"A comprehensive genome-scale reconstruction of Escherichia coli metabolism\u20132011","volume":"7","author":"Orth","year":"2011","journal-title":"Mol. Syst. Biol"},{"key":"2023020112472048400_btw132-B23","doi-asserted-by":"crossref","first-page":"2172","DOI":"10.1529\/biophysj.104.043000","article-title":"Uniform sampling of steady-state flux spaces: means to design experiments and to interpret enzymopathies","volume":"87","author":"Price","year":"2004","journal-title":"Biophys. J"},{"key":"2023020112472048400_btw132-B24","doi-asserted-by":"crossref","first-page":"3919","DOI":"10.1529\/biophysj.105.072645","article-title":"Candidate states of Helicobacter pylori's genome-scale metabolic network upon application of \u201cloop law'' thermodynamic constraints","volume":"90","author":"Price","year":"2006","journal-title":"Biophys. J"},{"key":"2023020112472048400_btw132-B25","doi-asserted-by":"crossref","first-page":"1797","DOI":"10.1101\/gr.2546004","article-title":"Genome-scale in silico models of E.coli have multiple equivalent phenotypic states: assessment of correlated reaction subsets that comprise network states","volume":"14","author":"Reed","year":"2004","journal-title":"Genome Res"},{"key":"2023020112472048400_btw132-B26","doi-asserted-by":"crossref","first-page":"e0135636","DOI":"10.1371\/journal.pone.0135636","article-title":"Obstructions to sampling qualitative properties","volume":"10","author":"Reimers","year":"2015","journal-title":"Plos One"},{"key":"2023020112472048400_btw132-B27","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1016\/j.bpj.2010.12.3707","article-title":"Elimination of thermodynamically infeasible loops in steady-state metabolic models","volume":"100","author":"Schellenberger","year":"2011","journal-title":"Biophys. J"},{"key":"2023020112472048400_btw132-B28","doi-asserted-by":"crossref","first-page":"5457","DOI":"10.1074\/jbc.R800048200","article-title":"Use of randomized sampling for analysis of metabolic networks","volume":"284","author":"Schellenberger","year":"2009","journal-title":"J. Biol. Chem"},{"key":"2023020112472048400_btw132-B29","doi-asserted-by":"crossref","first-page":"1290","DOI":"10.1038\/nprot.2011.308","article-title":"Quantitative prediction of cellular metabolism with constraint-based models: the COBRA Toolbox v2.0","volume":"6","author":"Schellenberger","year":"2011","journal-title":"Nat. Protoc"},{"key":"2023020112472048400_btw132-B30","doi-asserted-by":"crossref","first-page":"2532","DOI":"10.1038\/srep02532","article-title":"Understanding the interactions between bacteria in the human gut through metabolic modeling","volume":"3","author":"Shoaie","year":"2013","journal-title":"Sci. Rep. UK"},{"key":"2023020112472048400_btw132-B31","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s10107-003-0447-x","article-title":"How to compute the volume in high dimension?","volume":"97","author":"Simonovits","year":"2003","journal-title":"Math. Prog"},{"key":"2023020112472048400_btw132-B32","doi-asserted-by":"crossref","first-page":"1296","DOI":"10.1287\/opre.32.6.1296","article-title":"Efficient Monte-Carlo procedures for generating points uniformly distributed over bounded regions","volume":"32","author":"Smith","year":"1984","journal-title":"Oper. Res"},{"key":"2023020112472048400_btw132-B33","doi-asserted-by":"crossref","first-page":"5818","DOI":"10.1128\/JB.187.16.5818-5830.2005","article-title":"Expanded metabolic reconstruction of Helicobacter pylori (iIT341 GSM\/GPR): an in silico genome-scale characterization of single- and double-deletion mutants","volume":"187","author":"Thiele","year":"2005","journal-title":"J. Bacteriol"},{"key":"2023020112472048400_btw132-B34","doi-asserted-by":"crossref","first-page":"3925","DOI":"10.1038\/srep03925","article-title":"Network reconstruction of platelet metabolism identifies metabolic signature for aspirin resistance","volume":"4","author":"Thomas","year":"2014","journal-title":"Sci. Rep"},{"key":"2023020112472048400_btw132-B35","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0005-2728(97)00034-0","article-title":"Alternative respiratory pathways of Escherichia coli: energetics and transcriptional regulation in response to electron acceptors","volume":"1320","author":"Unden","year":"1997","journal-title":"Biochim. Biophys. Acta Bioenerg"},{"key":"2023020112472048400_btw132-B36","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1016\/j.jtbi.2004.02.006","article-title":"Monte Carlo sampling can be used to determine the size and shape of the steady-state flux space","volume":"228","author":"Wiback","year":"2004","journal-title":"J. Theor. Biol"},{"key":"2023020112472048400_btw132-B37","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1093\/bib\/bbp068","article-title":"Comparative study of computational methods to detect the correlated reaction sets in biochemical networks","volume":"12","author":"Xi","year":"2011","journal-title":"Brief. Bioinf"},{"key":"2023020112472048400_btw132-B38","doi-asserted-by":"crossref","first-page":"1544","DOI":"10.1126\/science.1174671","article-title":"Three-dimensional structural view of the central metabolic network of Thermotoga maritima","volume":"325","author":"Zhang","year":"2009","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/15\/2330\/49019959\/bioinformatics_32_15_2330.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/15\/2330\/49019959\/bioinformatics_32_15_2330.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,15]],"date-time":"2024-06-15T00:00:19Z","timestamp":1718409619000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/15\/2330\/1743212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,11]]},"references-count":38,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2016,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw132","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,8,1]]},"published":{"date-parts":[[2016,3,11]]}}}