Abstract
Flux balance analysis (FBA) is one of the most often applied methods on genome-scale metabolic networks. Although FBA uniquely determines the optimal yield, the pathway that achieves this is usually not unique. The analysis of the optimal-yield flux space has been an open challenge. Flux variability analysis is only capturing some properties of the flux space, while elementary mode analysis is intractable due to the enormous number of elementary modes. However, it has been found by Kelk et al. 2012, that the space of optimal-yield fluxes decomposes into flux modules. These decompositions allow a much easier but still comprehensive analysis of the optimal-yield flux space.
Using the mathematical definition of module introduced by Müller and Bockmayr 2013, we discovered that flux modularity is rather a local than a global property which opened connections to matroid theory. Specifically, we show that our modules correspond one-to-one to so-called separators of an appropriate matroid. Employing efficient algorithms developed in matroid theory we are now able to compute the decomposition into modules in a few seconds for genome-scale networks. Using that every module can be represented by one reaction that represents its function, in this paper, we also present a method that uses this decomposition to visualize the interplay of modules. We expect the new method to replace flux variability analysis in the pipelines for metabolic networks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete & Computational Geometry 8(1), 295–313 (1992)
Beard, D.A., Babson, E., Curtis, E., Qian, H.: Thermodynamic constraints for biochemical networks. Journal of Theoretical Biology 228, 327–333 (2004)
Burgard, A.P., Vaidyaraman, S., Maranas, C.D.: Minimal reaction sets for escherichia coli metabolism under different growth requirements and uptake environments. Biotechnology Progress 17, 791–797 (2001)
Cunningham, W.H.: A combinatorial decomposition theory. PhD thesis, University of Waterloo, Ontario, Canada (1973)
Feist, A.M., Palsson, B.Ø.: The biomass objective function. Current Opinion in Microbiology 13, 344–349 (2010)
Fukuda, K., Prodon, A.: Double description method revisited. In: Deza, M., Manoussakis, I., Euler, R. (eds.) CCS 1995. LNCS, vol. 1120, pp. 91–111. Springer, Heidelberg (1996)
Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.-P.: A technique for drawing directed graphs. IEEE Transactions on Software Engineering 19(3), 214–230 (1993)
Gansner, E.R., North, S.C.: An open graph visualization system and its applications to software engineering. Software - Practice and Experience 30(11), 1203–1233 (2000)
Kelk, S.M., Olivier, B.G., Stougie, L., Bruggeman, F.J.: Optimal flux spaces of genome-scale stoichiometric models are determined by a few subnetworks. Scientific Reports 2, 580 (2012)
Khachiyan, L., Boros, E., Borys, K., Elbassioni, K., Gurvich, V.: Generating all vertices of a polyhedron is hard. Discrete Computational Geometry 39, 174–190 (2008)
Khannapho, C., Zhao, H., Bonde, B.L., Kierzek, A.M., Avignone-Rossa, C.A., Bushell, M.E.: Selection of objective function in genome scale flux balance analysis for process feed development in antibiotic production. Metabolic Engineering 10(5), 227–233 (2008)
Krogdahl, S.: The dependence graph for bases in matroids. Discrete Mathematics 19, 47–59 (1977)
Mahadevan, R., Schilling, C.H.: The effects of alternate optimal solutions in constraint-based genome-scale metabolic models. Metabolic Engineering 5, 264–276 (2003)
Müller, A.C., Bockmayr, A.: Fast thermodynamically constrainted flux variability analysis. Bioinformatics 29(7), 903–909 (2013)
Müller, A.C., Bockmayr, A.: Flux modules in metabolic networks. Journal of Mathematical Biology (2013) (in press, preprint), http://nbn-resolving.de/urn:nbn:de:0296-matheon-12084
Oliveira, J.S., Bailey, C.G., Jones-Oliveira, J.B., Dixon, D.A.: An algebraic-combinatorial model for the identification and mapping of biochemical pathways. Bulletin of Mathematical Biology 63, 1163–1196 (2001)
Orth, J.D., Thiele, I., Palsson, B.Ø.: What is flux balance analysis. Nature Biotechnology 28, 245–248 (2010)
Oxley, J.: Matroid Theory, 2nd edn. Oxford Graduate Texts in Mathematics. Oxford University Press, New York (2011)
Jason Papin, A., Stelling, J., Price, N.D., Klamt, S., Schuster, S., Palsson, B.Ø.: Palsson. Comparison of network-based pathway analysis methods. Trends in Biotechnology 22(8), 400–405 (2004)
Price, N.D., Reed, J.L., Palsson, B.Ø.: Genome-scale models of microbial cells: evaluating the consequences of constraints. Nature Reviews Microbiology 2, 886–897 (2004)
Santos, F., Boele, J., Teusink, B.: A practical guide to genome-scale metabolic models and their analysis. Methods in Enzymology 500, 509 (2011)
Schellenberger, J., Que, R., Fleming, R.M.T., Thiele, I., Orth, J.D., Feist, A.M., Zielinski, D.C., Bordbar, A., Lewis, N.E., Rahmanian, S., Kang, J., Hyduke, D.R., Palsson, B.Ø.: Quantitative prediction of cellular metabolism with constraint-based models: the COBRA toolbox v2.0. Nature Protocols 6(9), 1290–1307 (2011)
Schuster, S., Hilgetag, C.: On elementary flux modes in biochemical systems at steady state. J. Biol. Systems 2, 165–182 (1994)
Schuster, S., Schuster, R.: Detecting strictly detailed balanced subnetworks in open chemical reaction networks. Journal of Mathematical Chemistry 6, 17–40 (1991)
Terzer, M.: Large scale methods to enumerate extreme rays and elementary modes. PhD thesis, Diss., Eidgenössische Technische Hochschule ETH Zürich, Nr. 18538, 2009 (2009)
Terzer, M., Stelling, J.: Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics 24(19), 2229–2235 (2008)
Truemper, K.: Partial matroid representations. European Journal of Combinatorics (1984)
Varma, A., Palsson, B.Ø.: Metabolic flux balancing: Basic concepts, scientific and practical use. Nature Biotechnology 12, 994–998 (1994)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Müller, A.C., Bruggeman, F.J., Olivier, B.G., Stougie, L. (2014). Fast Flux Module Detection Using Matroid Theory. In: Sharan, R. (eds) Research in Computational Molecular Biology. RECOMB 2014. Lecture Notes in Computer Science(), vol 8394. Springer, Cham. https://doi.org/10.1007/978-3-319-05269-4_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-05269-4_16
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-05268-7
Online ISBN: 978-3-319-05269-4
eBook Packages: Computer ScienceComputer Science (R0)