{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T21:59:59Z","timestamp":1717192799949},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2008,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>Cellular metabolism is one of the most investigated system of biological interactions. While the topological nature of individual reactions and pathways in the network is quite well understood there is still a lack of comprehension regarding the global functional behavior of the system. In the last few years flux-balance analysis (FBA) has been the most successful and widely used technique for studying metabolism at system level. This method strongly relies on the hypothesis that the organism maximizes an objective function. However only under very specific biological conditions (<jats:italic>e.g<\/jats:italic>. maximization of biomass for <jats:italic>E. coli<\/jats:italic> in reach nutrient medium) the cell seems to obey such optimization law. A more refined analysis not assuming extremization remains an elusive task for large metabolic systems due to algorithmic limitations.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>In this work we propose a novel algorithmic strategy that provides an efficient characterization of the whole set of stable fluxes compatible with the metabolic constraints. Using a technique derived from the fields of statistical physics and information theory we designed a message-passing algorithm to estimate the size of the affine space containing all possible steady-state flux distributions of metabolic networks. The algorithm, based on the well known Bethe approximation, can be used to approximately compute the volume of a non full-dimensional convex polytope in high dimensions. We first compare the accuracy of the predictions with an exact algorithm on small random metabolic networks. We also verify that the predictions of the algorithm match closely those of Monte Carlo based methods in the case of the Red Blood Cell metabolic network. Then we test the effect of gene knock-outs on the size of the solution space in the case of <jats:italic>E. coli<\/jats:italic> central metabolism. Finally we analyze the statistical properties of the average fluxes of the reactions in the <jats:italic>E. coli<\/jats:italic> metabolic network.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>We propose a novel efficient distributed algorithmic strategy to estimate the size and shape of the affine space of a non full-dimensional convex polytope in high dimensions. The method is shown to obtain, quantitatively and qualitatively compatible results with the ones of standard algorithms (where this comparison is possible) being still efficient on the analysis of large biological systems, where exact deterministic methods experience an explosion in algorithmic time. The algorithm we propose can be considered as an alternative to Monte Carlo sampling methods.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-9-240","type":"journal-article","created":{"date-parts":[[2008,5,20]],"date-time":"2008-05-20T06:14:39Z","timestamp":1211264079000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":32,"title":["Estimating the size of the solution space of metabolic networks"],"prefix":"10.1186","volume":"9","author":[{"given":"Alfredo","family":"Braunstein","sequence":"first","affiliation":[]},{"given":"Roberto","family":"Mulet","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Pagnani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2008,5,19]]},"reference":[{"issue":"6804","key":"2225_CR1","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1038\/35036627","volume":"407","author":"H Jeong","year":"2000","unstructured":"Jeong H, Tombor B, Albert R, Oltvai ZN, Barabasi AL: The large-scale organization of metabolic networks. Nature 2000, 407(6804):651\u2013654. 10.1038\/35036627","journal-title":"Nature"},{"key":"2225_CR2","doi-asserted-by":"publisher","first-page":"1121","DOI":"10.1038\/81025","volume":"18","author":"DA Fell","year":"2000","unstructured":"Fell DA, Wagner A: The small world of metabolism. Nature Biotechnology 2000, 18: 1121\u20131122. 10.1038\/81025","journal-title":"Nature Biotechnology"},{"key":"2225_CR3","doi-asserted-by":"crossref","unstructured":"Z D, Qin ZS: Structural comparison of metabolic networks in selected single cell organisms. BMC Bioinformatics 2005., 6(8):","DOI":"10.1186\/1471-2105-6-8"},{"key":"2225_CR4","doi-asserted-by":"publisher","first-page":"D354","DOI":"10.1093\/nar\/gkj102","volume":"34","author":"M Kanehisa","year":"2006","unstructured":"Kanehisa M, Goto S, Hattori M, Aoki-Kinoshita K, Itoh M, Kawashima S, Katayama T, Araki M, Hirakawa M: From genomics to chemical genomics: new developments in KEGG. Nucleic Acids Res 2006, 34: D354\u20137. 10.1093\/nar\/gkj102","journal-title":"Nucleic Acids Res"},{"key":"2225_CR5","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1038\/nature01149","volume":"420","author":"AU Ibarra","year":"2002","unstructured":"Ibarra AU, Edwards J, Palsson B: Escherichia coli K-12 undergoes adaptive evolution to achieve in silico predicted optimal growth. Nature 2002, 420: 186\u2013189. 10.1038\/nature01149","journal-title":"Nature"},{"key":"2225_CR6","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1006\/jtbi.1993.1202","volume":"165","author":"A Varma","year":"1993","unstructured":"Varma A, Palsson B: Metabolic Capabilities of Escherichia coli: I.Synthesis of biosynthetic precursors and cofactors. J theor Biol 1993, 165: 477\u2013502. 10.1006\/jtbi.1993.1202","journal-title":"J theor Biol"},{"key":"2225_CR7","doi-asserted-by":"publisher","first-page":"15112","DOI":"10.1073\/pnas.232349399","volume":"99","author":"D Segr\u00e9","year":"2002","unstructured":"Segr\u00e9 D, Vitkup D, Church G: Analysis of optimality in natural and perturbed metabolic networks. PNAS 2002, 99: 15112\u201315117. 10.1073\/pnas.232349399","journal-title":"PNAS"},{"key":"2225_CR8","unstructured":"LRS package[http:\/\/cgm.cs.mcgill.ca\/~avis\/C\/lrs.html]"},{"issue":"3","key":"2225_CR9","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF02293050","volume":"8","author":"D Avis","year":"1992","unstructured":"Avis D, Fukuda K: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput Geom 1992, 8(3):295\u2013313. 10.1007\/BF02293050","journal-title":"Discrete Comput Geom"},{"key":"2225_CR10","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1016\/j.jtbi.2004.02.006","volume":"228","author":"S Wiback","year":"2004","unstructured":"Wiback S, Famili I, Greenberg HJ, Palsson B: Monte Carlo sampling can be used to determine the size and shape of the steady-state flux space. J Theor Biol 2004, 228: 437\u2013447. 10.1016\/j.jtbi.2004.02.006","journal-title":"J Theor Biol"},{"key":"2225_CR11","doi-asserted-by":"publisher","first-page":"2172","DOI":"10.1529\/biophysj.104.043000","volume":"87","author":"N Price","year":"2004","unstructured":"Price N, Schellenberger J, Palsson B: Uniform Sampling of Steady-State Flux Spaces: Means to Design Experiments and to Interpret Enzymopathies. Biophysical Journal 2004, 87: 2172\u20132186. 10.1529\/biophysj.104.043000","journal-title":"Biophysical Journal"},{"key":"2225_CR12","doi-asserted-by":"publisher","first-page":"11683","DOI":"10.1074\/jbc.M409072200","volume":"280","author":"I Thiele","year":"2005","unstructured":"Thiele I, Price N, Vo T, Palsson B: Impact of diabetes, ischemia, and diet. J Biol Chem 2005, 280: 11683\u201311695. 10.1074\/jbc.M409072200","journal-title":"J Biol Chem"},{"key":"2225_CR13","doi-asserted-by":"publisher","first-page":"3919","DOI":"10.1529\/biophysj.105.072645","volume":"90","author":"N Price","year":"2006","unstructured":"Price N, Thiele I, Palsson B: Candidate States of Helicobacter pylori's Genome-Scale Metabolic Network upon Application of \"Loop Law\" Thermodynamic Constraints. Biophysical Journal 2006, 90: 3919\u20133928. 10.1529\/biophysj.105.072645","journal-title":"Biophysical Journal"},{"key":"2225_CR14","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1038\/nature02289","volume":"427","author":"E Almaas","year":"2004","unstructured":"Almaas E, Kovacs B, Vicsek T, Oltval Z, Barabasi AL: Global organization of metabolic fluxes in the bacterium Escherichia col. Nature 2004, 427: 839\u2013843. 10.1038\/nature02289","journal-title":"Nature"},{"issue":"1\u20132","key":"2225_CR15","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s10107-003-0447-x","volume":"97","author":"M Simonovits","year":"2003","unstructured":"Simonovits M: How to compute the volume in high dimension? Math Progr 2003, 97(1\u20132):337\u2013374.","journal-title":"Math Progr"},{"issue":"5","key":"2225_CR16","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1137\/0217060","volume":"17","author":"M Dyer","year":"1988","unstructured":"Dyer M, Frieze A: On the complexity of computing the volume of a polyhedron. SIAM J Comput 1988, 17(5):967\u201397. 10.1137\/0217060","journal-title":"SIAM J Comput"},{"key":"2225_CR17","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-642-58043-7_5","volume-title":"New trends in discrete and computational geometry, Springer-Verlag","author":"L Khachiyan","year":"1993","unstructured":"Khachiyan L: Complexity of volume computation. In New trends in discrete and computational geometry, Springer-Verlag Edited by: Pach J. 1993, 91\u2013101."},{"key":"2225_CR18","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-0348-8438-9_6","volume-title":"Polytopes-combinatorics and computation, Birkhauser","author":"B B\u00ebuler","year":"2000","unstructured":"B\u00ebuler B, Enge A, Fukuda K: Exact volume computation for convex polytopes: A practical study. In Polytopes-combinatorics and computation, Birkhauser Edited by: Ziegler GM, Kalai G. 2000, 131\u2013154."},{"key":"2225_CR19","first-page":"772","volume-title":"Advances in Neural Information Processing Systems (NIPS) 13, Denver, CO","author":"J Yedidia","year":"2001","unstructured":"Yedidia J, Freeman W, Weiss Y: Generalized belief propagation. In Advances in Neural Information Processing Systems (NIPS) 13, Denver, CO Edited by: press M. 2001, 772\u2013778."},{"issue":"2","key":"2225_CR20","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"FR Kschischang","year":"2001","unstructured":"Kschischang FR, Frey BJ, Loeliger HA: Factor graphs and the sum-product algorithm. Information Theory, IEEE Transactions on 2001, 47(2):498\u2013519. 10.1109\/18.910572","journal-title":"Information Theory, IEEE Transactions on"},{"key":"2225_CR21","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1002\/rsa.20057","volume":"27","author":"A Braunstein","year":"2005","unstructured":"Braunstein A, Mezard M, Zecchina R: Survey propagation: An algorithm for satisfiability. Random Struct Algorithms 2005, 27: 201\u2013226. 10.1002\/rsa.20057","journal-title":"Random Struct Algorithms"},{"key":"2225_CR22","volume-title":"Information Theory, Inference, and Learning Algorithms","author":"DJC MacKay","year":"2003","unstructured":"MacKay DJC: Information Theory, Inference, and Learning Algorithms. Cambridge University Press; 2003."},{"issue":"9","key":"2225_CR23","doi-asserted-by":"publisher","first-page":"R54","DOI":"10.1186\/gb-2003-4-9-r54","volume":"4","author":"J Reed","year":"2003","unstructured":"Reed J, Vo T, Schilling C, Palsson B: An expanded genome-scale model of Escherichia coli K-12 (iJR904 GSM\/GPR). Genome Biology 2003, 4(9):R54. 10.1186\/gb-2003-4-9-r54","journal-title":"Genome Biology"},{"issue":"05","key":"2225_CR24","doi-asserted-by":"publisher","first-page":"P05012","DOI":"10.1088\/1742-5468\/2007\/05\/P05012","volume":"2007","author":"A De Martino","year":"2007","unstructured":"De Martino A, Martelli RMC, Castillo IP: Von Neumann expanding model on random graphs. Journal of Statistical Mechanics: Theory and Experiment 2007, 2007(05):P05012. 10.1088\/1742-5468\/2007\/05\/P05012","journal-title":"Journal of Statistical Mechanics: Theory and Experiment"},{"key":"2225_CR25","volume-title":"Technical report","author":"G Bianconi","year":"2007","unstructured":"Bianconi G, Zecchina R: Viable flux distribution in metabolic networks. Technical report 2007. ArXiv:cond-mat\/0705.2816 [http:\/\/aps.arxiv.org\/pdf\/0705.2816]"},{"key":"2225_CR26","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.jtbi.2004.01.008","volume":"228","author":"D Beard","year":"2004","unstructured":"Beard D, Babson E, Curtis E, Qian H: Thermodynamic constraints for biochemical networks. J Theor Biol 2004, 228: 327\u2013333. 10.1016\/j.jtbi.2004.01.008","journal-title":"J Theor Biol"},{"key":"2225_CR27","volume-title":"Exactly Solved Models in Statistical Mechanics","author":"B Baxter","year":"1989","unstructured":"Baxter B: Exactly Solved Models in Statistical Mechanics. London: Academic Press Inc; 1989."},{"key":"2225_CR28","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/PL00011099","volume":"20","author":"M Mezard","year":"2001","unstructured":"Mezard M, Parisi G: The Bethe lattice spin glass revisited. The European Physical Journal B 2001, 20: 217. 10.1007\/PL00011099","journal-title":"The European Physical Journal B"},{"key":"2225_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1023\/A:1022221005097","volume":"111","author":"M Mezard","year":"2003","unstructured":"Mezard M, Parisi G: The cavity method at zero temperature. J Stat Phys 2003, 111: 1. 10.1023\/A:1022221005097","journal-title":"J Stat Phys"},{"key":"2225_CR30","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/18.910577","volume":"47","author":"T Richardson","year":"2001","unstructured":"Richardson T, Urbanke R: The capacity of low-density parity check codes under message passing decoding. IEEE, Trans Info Theory 2001, 47: 599\u2013618. 10.1109\/18.910577","journal-title":"IEEE, Trans Info Theory"},{"issue":"10","key":"2225_CR31","doi-asserted-by":"publisher","first-page":"2173","DOI":"10.1162\/089976601750541769","volume":"13","author":"Y Weiss","year":"2001","unstructured":"Weiss Y, Freeman WT: Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology. Neural Comp 2001, 13(10):2173\u20132200. 10.1162\/089976601750541769","journal-title":"Neural Comp"},{"key":"2225_CR32","doi-asserted-by":"publisher","first-page":"11079","DOI":"10.1073\/pnas.0700324104","volume":"104","author":"C Baldassi","year":"2007","unstructured":"Baldassi C, Braunstein A, Brunel N, Zecchina R: Efficient supervised learning in networks with binary synapses. PNAS 2007, 104: 11079\u201311084. [http:\/\/aps.arxiv.org\/pdf\/0707.1295] 10.1073\/pnas.0700324104","journal-title":"PNAS"},{"key":"2225_CR33","doi-asserted-by":"publisher","first-page":"812","DOI":"10.1126\/science.1073287","volume":"297","author":"M Mezard","year":"2002","unstructured":"Mezard M, Parisi G, Zecchina R: Analytic and Algorithmic Solution of Random Satisfiability Problems. Science 2002, 297: 812. [http:\/\/aps.arxiv.org\/pdf\/0707.1295] 10.1126\/science.1073287","journal-title":"Science"},{"key":"2225_CR34","doi-asserted-by":"publisher","first-page":"268701","DOI":"10.1103\/PhysRevLett.89.268701","volume":"89","author":"R Mulet","year":"2002","unstructured":"Mulet R, Pagnani A, Weigt M, Zecchina R: Coloring random graphs. Phys Rev Lett 2002, 89: 268701. [http:\/\/arxiv.org\/abs\/cond-mat\/0208460] 10.1103\/PhysRevLett.89.268701","journal-title":"Phys Rev Lett"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-9-240.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T04:00:21Z","timestamp":1630468821000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-9-240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,5,19]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["2225"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-9-240","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,5,19]]},"assertion":[{"value":"10 September 2007","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2008","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2008","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"240"}}