{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T00:40:46Z","timestamp":1771461646170,"version":"3.50.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"24","license":[{"start":{"date-parts":[[2016,11,16]],"date-time":"2016-11-16T00:00:00Z","timestamp":1479254400000},"content-version":"vor","delay-in-days":84,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"Becas-Chile, UQ Centennial and IPRS Scholarship Programmes"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,12,15]]},"abstract":"<jats:p>Motivation: Computation of steady-state flux solutions in large metabolic models is routinely performed using flux balance analysis based on a simple LP (Linear Programming) formulation. A minimal requirement for thermodynamic feasibility of the flux solution is the absence of internal loops, which are enforced using \u2018loopless constraints\u2019. The resulting loopless flux problem is a substantially harder MILP (Mixed Integer Linear Programming) problem, which is computationally expensive for large metabolic models.<\/jats:p>\n               <jats:p>Results: We developed a pre-processing algorithm that significantly reduces the size of the original loopless problem into an easier and equivalent MILP problem. The pre-processing step employs a fast matrix sparsification algorithm\u2014Fast- sparse null-space pursuit (SNP)\u2014inspired by recent results on SNP. By finding a reduced feasible \u2018loop-law\u2019 matrix subject to known directionalities, Fast-SNP considerably improves the computational efficiency in several metabolic models running different loopless optimization problems. Furthermore, analysis of the topology encoded in the reduced loop matrix enabled identification of key directional constraints for the potential permanent elimination of infeasible loops in the underlying model. Overall, Fast-SNP is an effective and simple algorithm for efficient formulation of loop-law constraints, making loopless flux optimization feasible and numerically tractable at large scale.<\/jats:p>\n               <jats:p>Availability and Implementation: Source code for MATLAB including examples is freely available for download at http:\/\/www.aibn.uq.edu.au\/cssb-resources under Software. Optimization uses Gurobi, CPLEX or GLPK (the latter is included with the algorithm).<\/jats:p>\n               <jats:p>Contact: \u00a0lars.nielsen@uq.edu.au<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw555","type":"journal-article","created":{"date-parts":[[2016,8,25]],"date-time":"2016-08-25T02:49:07Z","timestamp":1472093347000},"page":"3807-3814","source":"Crossref","is-referenced-by-count":16,"title":["Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models"],"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, Corner College and Cooper Rds (Bldg 75), Australia"}]},{"given":"Lars K.","family":"Nielsen","sequence":"additional","affiliation":[{"name":"Australian Institute for Bioengineering and Nanotechnology (AIBN), The University of Queensland, Corner College and Cooper Rds (Bldg 75), Australia"}]}],"member":"286","published-online":{"date-parts":[[2016,8,24]]},"reference":[{"key":"2023020114103474700_btw555-B1","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.jtbi.2004.01.008","article-title":"Thermodynamic constraints for biochemical networks","volume":"228","author":"Beard","year":"2004","journal-title":"J. Theor. Biol"},{"key":"2023020114103474700_btw555-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":"2023020114103474700_btw555-B3","first-page":"3781","author":"Bian","year":"2015"},{"key":"2023020114103474700_btw555-B4","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1186\/1752-0509-5-180","article-title":"A multi-tissue type genome-scale metabolic network for analysis of whole-body systems physiology","volume":"5","author":"Bordbar","year":"2011","journal-title":"Bmc Syst. Biol"},{"key":"2023020114103474700_btw555-B5","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":"Mol. Syst. Biol"},{"key":"2023020114103474700_btw555-B6","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1038\/nrg3643","article-title":"Constraint-based models predict metabolic and associated cellular functions","volume":"15","author":"Bordbar","year":"2014","journal-title":"Nat. Rev. Genet"},{"key":"2023020114103474700_btw555-B7","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":"2023020114103474700_btw555-B8","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1137\/0607059","article-title":"The null space problem. 1. Complexity","volume":"7","author":"Coleman","year":"1986","journal-title":"Siam J. Algebra Discr"},{"key":"2023020114103474700_btw555-B9","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1104\/pp.109.148817","article-title":"AraGEM, a genome-scale reconstruction of the primary metabolic network in arabidopsis","volume":"152","author":"Dal'Molin","year":"2010","journal-title":"Plant Physiol"},{"key":"2023020114103474700_btw555-B10","doi-asserted-by":"crossref","first-page":"1871","DOI":"10.1104\/pp.110.166488","article-title":"C4GEM, a genome-scale metabolic model to study C-4 plant metabolism","volume":"154","author":"Dal\u2019Molin","year":"2010","journal-title":"Plant Physiol"},{"key":"2023020114103474700_btw555-B11","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":"2023020114103474700_btw555-B12","doi-asserted-by":"crossref","first-page":"946","DOI":"10.3390\/metabo3040946","article-title":"Counting and correcting thermodynamically infeasible flux cycles in genome-scale metabolic networks","volume":"3","author":"De Martino","year":"2013","journal-title":"Metabolites"},{"key":"2023020114103474700_btw555-B13","doi-asserted-by":"crossref","first-page":"2159","DOI":"10.1093\/bioinformatics\/btv096","article-title":"CycleFreeFlux: efficient removal of thermodynamically infeasible loops from flux distributions","volume":"31","author":"Desouki","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020114103474700_btw555-B14","doi-asserted-by":"crossref","first-page":"1777","DOI":"10.1073\/pnas.0610772104","article-title":"Global reconstruction of the human metabolic network based on genomic and bibliomic data","volume":"104","author":"Duarte","year":"2007","journal-title":"Porc. Natl. Acad. Sci. USA"},{"key":"2023020114103474700_btw555-B15","doi-asserted-by":"crossref","first-page":"5528","DOI":"10.1073\/pnas.97.10.5528","article-title":"The Escherichia coli MG1655 in silico metabolic genotype: Its definition, characteristics, and capabilities","volume":"97","author":"Edwards","year":"2000","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020114103474700_btw555-B16","doi-asserted-by":"crossref","first-page":"2006.0004","DOI":"10.1038\/msb4100046","article-title":"Modeling methanogenesis with a genome-scale metabolic reconstruction of Methanosarcina barkeri","volume":"2","author":"Feist","year":"2006","journal-title":"Mol. Syst. Biol"},{"key":"2023020114103474700_btw555-B17","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1101\/gr.234503","article-title":"Genome-scale reconstruction of the Saccharomyces cerevisiae metabolic network","volume":"13","author":"Forster","year":"2003","journal-title":"Genome Res"},{"key":"2023020114103474700_btw555-B18","first-page":"205","article-title":"Matrix sparsification and the sparse null space problem","volume":"6302","author":"Gottlieb","year":"2010","journal-title":"Approx. Random. Comb. Optim"},{"key":"2023020114103474700_btw555-B19","doi-asserted-by":"crossref","first-page":"724","DOI":"10.3389\/fpls.2014.00724","article-title":"Integration of a constraint-based metabolic model of Brassica napus developing seeds with C-13-metabolic flux analysis","volume":"5","author":"Hay","year":"2014","journal-title":"Front. Plant Sci"},{"key":"2023020114103474700_btw555-B20","first-page":"bat059","article-title":"Version 6 of the consensus yeast metabolic network refines biochemical coverage and improves model performance","volume":"2013","author":"Heavner","year":"2013","journal-title":"Database-Oxford"},{"key":"2023020114103474700_btw555-B21","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1126\/science.1132067","article-title":"Multiple high-throughput analyses monitor the response of E. coli to perturbations","volume":"316","author":"Ishii","year":"2007","journal-title":"Science"},{"key":"2023020114103474700_btw555-B22","doi-asserted-by":"crossref","first-page":"26.","DOI":"10.1186\/1752-0509-1-26","article-title":"Investigating the metabolic capabilities of Mycobacterium tuberculosis H37Rv using the in silico strain iNJ661 and proposing alternative drug targets","volume":"1","author":"Jamshidi","year":"2007","journal-title":"Bmc Syst. Biol"},{"key":"2023020114103474700_btw555-B23","doi-asserted-by":"crossref","first-page":"D515","DOI":"10.1093\/nar\/gkv1049","article-title":"BiGG models: a platform for integrating, standardizing and sharing genome-scale models","volume":"44","author":"King","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023020114103474700_btw555-B24","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":"2023020114103474700_btw555-B25","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":"2023020114103474700_btw555-B26","doi-asserted-by":"crossref","first-page":"1710","DOI":"10.1128\/JB.01218-10","article-title":"An experimentally validated genome-scale metabolic reconstruction of Klebsiella pneumoniae MGH 78578, iYL1228","volume":"193","author":"Liao","year":"2011","journal-title":"J. Bacteriol"},{"key":"2023020114103474700_btw555-B27","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1016\/j.ymben.2003.09.002","article-title":"The effects of alternate optimal solutions in constraint-based genome-scale metabolic models","volume":"5","author":"Mahadevan","year":"2003","journal-title":"Metab. Eng"},{"key":"2023020114103474700_btw555-B28","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1093\/bioinformatics\/btt059","article-title":"Fast thermodynamically constrained flux variability analysis","volume":"29","author":"M\u00fcller","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020114103474700_btw555-B29","doi-asserted-by":"crossref","first-page":"140.","DOI":"10.1186\/1752-0509-6-140","article-title":"A proof for loop-law constraints in stoichiometric metabolic networks","volume":"6","author":"Noor","year":"2012","journal-title":"Bmc Syst. Biol"},{"key":"2023020114103474700_btw555-B30","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1006\/bulm.2001.0263","article-title":"An algebraic-combinatorial model for the identification and mapping of biochemical pathways","volume":"63","author":"Oliveira","year":"2001","journal-title":"B. Math. Biol"},{"key":"2023020114103474700_btw555-B31","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1038\/msb.2011.65","article-title":"A comprehensive genome-scale reconstruction of Escherichia coli metabolism - 2011","volume":"7","author":"Orth","year":"2011","journal-title":"Mol. Syst. Biol"},{"key":"2023020114103474700_btw555-B32","doi-asserted-by":"crossref","first-page":"1.","DOI":"10.1128\/ecosalplus.10.2.1","article-title":"Reconstruction and use of microbial metabolic networks: the core Escherichia coli metabolic model as an educational guide","volume":"4","author":"Orth","year":"2010","journal-title":"EcoSal plus"},{"key":"2023020114103474700_btw555-B33","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1038\/nbt.1614","article-title":"What is flux balance analysis?","volume":"28","author":"Orth","year":"2010","journal-title":"Nat Biotechnol"},{"key":"2023020114103474700_btw555-B34","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/btw132","article-title":"ll-ACHRB: a scalable algorithm for sampling the feasible solution space of metabolic networks","author":"Saa","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020114103474700_btw555-B35","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1287\/ijoc.6.4.445","article-title":"Preprocessing and probing techniques for mixed integer programming problems","volume":"6","author":"Savelsbergh","year":"1994","journal-title":"ORSA J. Comput"},{"key":"2023020114103474700_btw555-B36","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":"2023020114103474700_btw555-B37","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1038\/73786","article-title":"A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks","volume":"18","author":"Schuster","year":"2000","journal-title":"Nat. Biotechnol"},{"key":"2023020114103474700_btw555-B38","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1016\/j.cmet.2015.07.001","article-title":"Quantifying diet-induced metabolic changes of the human gut microbiome","volume":"22","author":"Shoaie","year":"2015","journal-title":"Cell Metab"},{"key":"2023020114103474700_btw555-B39","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1038\/msb4100131","article-title":"Metabolic modeling of a mutualistic microbial community","volume":"3","author":"Stolyar","year":"2007","journal-title":"Mol. Syst. Biol"},{"key":"2023020114103474700_btw555-B40","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1186\/1752-0509-5-8","article-title":"A community effort towards a knowledge-base and mathematical model of the human pathogen Salmonella Typhimurium LT2","volume":"5","author":"Thiele","year":"2011","journal-title":"Bmc Syst. Biol"},{"key":"2023020114103474700_btw555-B41","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1038\/ismej.2010.117","article-title":"Genome-scale dynamic modeling of the competition between Rhodoferax and Geobacter in anoxic subsurface environments","volume":"5","author":"Zhuang","year":"2011","journal-title":"Isme J"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/24\/3807\/49027163\/bioinformatics_32_24_3807.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/24\/3807\/49027163\/bioinformatics_32_24_3807.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:01:48Z","timestamp":1675296108000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/24\/3807\/2525667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,24]]},"references-count":41,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2016,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw555","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2016,12,15]]},"published":{"date-parts":[[2016,8,24]]}}}