Document Open Access Logo

Geometric Algorithms for Sampling the Flux Space of Metabolic Networks

Authors Apostolos Chalkis , Vissarion Fisikopoulos , Elias Tsigaridas, Haris Zafeiropoulos

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.21.pdf
  • Filesize: 2.19 MB
  • 16 pages

Document Identifiers

Author Details

Apostolos Chalkis
  • Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Greece
  • Athena Research Innovation Center, Athens, Greece
Vissarion Fisikopoulos
  • Department of Informatics and Telecommunications, National and Kapodistrian University of Athens, Greece
Elias Tsigaridas
  • Inria Paris and IMJ-PRG, Sorbonne Université, France
  • Paris Université, France
Haris Zafeiropoulos
  • Department of Biology, University of Crete, Heraklion, Greece
  • Institute of Marine Biology, Biotechnology and Aquaculture, Hellenic Centre for Marine Research, Anavyssos Attiki, Greece

Funding

  • Chalkis, Apostolos: Supported by PeGASUS.
  • Tsigaridas, Elias: Partially supported by ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA and the PHC GRAPE.

Acknowledgements

We would like to thank the anonymous reviewers for their helpful comments and suggestions. We also thank Ioannis Emiris for his useful comments.

Cite AsGet BibTex

Apostolos Chalkis, Vissarion Fisikopoulos, Elias Tsigaridas, and Haris Zafeiropoulos. Geometric Algorithms for Sampling the Flux Space of Metabolic Networks. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.21

Abstract

Systems Biology is a fundamental field and paradigm that introduces a new era in Biology. The crux of its functionality and usefulness relies on metabolic networks that model the reactions occurring inside an organism and provide the means to understand the underlying mechanisms that govern biological systems. Even more, metabolic networks have a broader impact that ranges from resolution of ecosystems to personalized medicine. The analysis of metabolic networks is a computational geometry oriented field as one of the main operations they depend on is sampling uniformly points from polytopes; the latter provides a representation of the steady states of the metabolic networks. However, the polytopes that result from biological data are of very high dimension (to the order of thousands) and in most, if not all, the cases are considerably skinny. Therefore, to perform uniform random sampling efficiently in this setting, we need a novel algorithmic and computational framework specially tailored for the properties of metabolic networks. We present a complete software framework to handle sampling in metabolic networks. Its backbone is a Multiphase Monte Carlo Sampling (MMCS) algorithm that unifies rounding and sampling in one pass, obtaining both upon termination. It exploits an improved variant of the Billiard Walk that enjoys faster arithmetic complexity per step. We demonstrate the efficiency of our approach by performing extensive experiments on various metabolic networks. Notably, sampling on the most complicated human metabolic network accessible today, Recon3D, corresponding to a polytope of dimension 5335, took less than 30 hours. To our knowledge, that is out of reach for existing software.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Mathematical software
  • Applied computing → Systems biology
  • Computing methodologies → Modeling and simulation
Keywords
  • Flux analysis
  • metabolic networks
  • convex polytopes
  • random walks
  • sampling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Radosław Adamczak, Alexander Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann. Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles. Journal of the American Mathematical Society, 23(2):535-561, 2010. URL: https://doi.org/10.1090/S0894-0347-09-00650-X.
  2. MOSEK ApS. The MOSEK optimization toolbox for R manual. Version 9.2, 2019. URL: https://docs.mosek.com/9.2/rmosek/index.html.
  3. Shiri Artstein-Avidan, Haim Kaplan, and Micha Sharir. On radial isotropic position: Theory and algorithms, 2020. URL: http://arxiv.org/abs/2005.04918.
  4. David B Bernstein, Floyd E Dewhirst, and Daniel Segre. Metabolic network percolation quantifies biosynthetic capabilities across the human oral microbiome. Elife, 8:e39733, 2019. Google Scholar
  5. Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. J. ACM, 51(4):540–556, 2004. URL: https://doi.org/10.1145/1008731.1008733.
  6. Sergio Bordel, Rasmus Agren, and Jens Nielsen. Sampling the solution space in genome-scale metabolic networks reveals transcriptional regulation in key enzymes. PLOS Computational Biology, 6(7):1-13, July 2010. URL: https://doi.org/10.1371/journal.pcbi.1000859.
  7. Elizabeth Brunk, Swagatika Sahoo, Daniel C Zielinski, Ali Altunkaya, Andreas Dräger, Nathan Mih, Francesco Gatto, Avlant Nilsson, German Andres Preciat Gonzalez, Maike Kathrin Aurich, et al. Recon3D enables a three-dimensional view of gene variation in human metabolism. Nature biotechnology, 36(3):272, 2018. Google Scholar
  8. Ali Cakmak, Xinjian Qi, A Ercument Cicek, Ilya Bederman, Leigh Henderson, Mitchell Drumm, and Gultekin Ozsoyoglu. A new metabolomics analysis technique: steady-state metabolic network dynamics analysis. Journal of bioinformatics and computational biology, 10(01):1240003, 2012. Google Scholar
  9. Ludovic Calès, Apostolos Chalkis, Ioannis Z. Emiris, and Vissarion Fisikopoulos. Practical Volume Computation of Structured Convex Bodies, and an Application to Modeling Portfolio Dependencies and Financial Crises. In Bettina Speckmann and Csaba D. Tóth, editors, 34th International Symposium on Computational Geometry (SoCG 2018), volume 99 of LIPIcs, pages 19:1-19:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.19.
  10. Apostolos Chalkis, Ioannis Z. Emiris, and Vissarion Fisikopoulos. Practical volume estimation by a new annealing schedule for cooling convex bodies, 2019. URL: http://arxiv.org/abs/1905.05494.
  11. Apostolos Chalkis, Ioannis Z. Emiris, and Vissarion Fisikopoulos. Practical volume estimation of zonotopes by a new annealing schedule for cooling convex bodies. In Anna Maria Bigatti, Jacques Carette, James H. Davenport, Michael Joswig, and Timo de Wolff, editors, Mathematical Software - ICMS 2020, pages 212-221, Cham, 2020. Springer International Publishing. Google Scholar
  12. Apostolos Chalkis and Vissarion Fisikopoulos. volesti: Volume approximation and sampling for convex polytopes in R, 2020. URL: http://arxiv.org/abs/2007.01578.
  13. Apostolos Chalkis, Vissarion Fisikopoulos, Elias Tsigaridas, and Haris Zafeiropoulos. Geometric algorithms for sampling the flux space of metabolic networks, 2021. URL: http://arxiv.org/abs/2012.05503.
  14. Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. Fast mcmc sampling algorithms on polytopes. Journal of Machine Learning Research, 19(55):1-86, 2018. URL: http://jmlr.org/papers/v19/18-158.html.
  15. A. Chevallier, S. Pion, and F. Cazals. Hamiltonian Monte Carlo with boundary reflections, and application to polytope volume calculations. Research Report RR-9222, INRIA Sophia Antipolis, France, 2018. URL: https://hal.archives-ouvertes.fr/hal-01919855.
  16. B. Cousins. Efficient high-dimensional sampling and integration. PhD thesis, Georgia Institute of Technology, Georgia, U.S.A., 2017. Google Scholar
  17. Ben Cousins and Santosh Vempala. A practical volume algorithm. Mathematical Programming Computation, 8(2):133-160, 2016. Google Scholar
  18. A. B. Dieker and Santosh S. Vempala. Stochastic billiards for sampling from the boundary of a convex set. Mathematics of Operations Research, 40(4):888-901, 2015. URL: http://www.jstor.org/stable/24540983.
  19. Shirin Fallahi, Hans J Skaug, and Guttorm Alendal. A comparison of Monte Carlo sampling methods for metabolic network models. PLOS One, 15(7):e0235393, 2020. Google Scholar
  20. Andrew Gelman and Donald B. Rubin. Inference from Iterative Simulation Using Multiple Sequences. Statistical Science, 7(4):457-472, 1992. Publisher: Institute of Mathematical Statistics. URL: https://www.jstor.org/stable/2246093.
  21. Charles J. Geyer. Practical Markov chain Monte Carlo. Statist. Sci., 7(4):473-483, November 1992. URL: https://doi.org/10.1214/ss/1177011137.
  22. Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-773, 2012. URL: http://jmlr.org/papers/v13/gretton12a.html.
  23. Elena Gryazina and Boris Polyak. Random sampling: Billiard walk algorithm. European Journal of Operational Research, 238(2):497-504, 2014. URL: https://doi.org/10.1016/j.ejor.2014.03.041.
  24. Gaël Guennebaud, Benoît Jacob, et al. Eigen v3, 2010. URL: http://eigen.tuxfamily.org.
  25. Hulda S Haraldsdóttir, Ben Cousins, Ines Thiele, Ronan MT Fleming, and Santosh Vempala. CHRR: coordinate hit-and-run with rounding for uniform sampling of constraint-based models. Bioinformatics, 33(11):1741-1743, 2017. Google Scholar
  26. Laurent Heirendt, Sylvain Arreckx, Thomas Pfau, Sebastián N Mendoza, Anne Richelle, Almut Heinken, Hulda S Haraldsdóttir, Jacek Wachowiak, Sarah M Keating, Vanja Vlasov, et al. Creation and analysis of biochemical constraint-based models using the cobra toolbox v. 3.0. Nature protocols, 14(3):639-702, 2019. Google Scholar
  27. Trey Ideker, Timothy Galitski, and Leroy Hood. A new approach to decoding life: systems biology. Annual review of genomics and human genetics, 2(1):343-372, 2001. Google Scholar
  28. Fritz John. Extremum Problems with Inequalities as Subsidiary Conditions. In Giorgio Giorgi and Tinne Hoff Kjeldsen, editors, Traces and Emergence of Nonlinear Programming, pages 197-215. Springer, Basel, 2014. URL: https://doi.org/10.1007/978-3-0348-0439-4_9.
  29. Adam Tauman Kalai and Santosh Vempala. Simulated annealing for convex optimization. Mathematics of Operations Research, 31(2):253-266, 2006. URL: http://www.jstor.org/stable/25151723.
  30. David E Kaufman and Robert L Smith. Direction choice for accelerated convergence in hit-and-run sampling. Operations Research, 46(1):84-95, 1998. Google Scholar
  31. Zachary A King, Justin Lu, Andreas Dräger, Philip Miller, Stephen Federowicz, Joshua A Lerman, Ali Ebrahim, Bernhard Ø. Palsson, and Nathan E Lewis. Bigg models: A platform for integrating, standardizing and sharing genome-scale models. Nucleic acids research, 44(D1):D515-D522, 2016. Google Scholar
  32. Edda Klipp, Wolfram Liebermeister, Christoph Wierling, and Axel Kowald. Systems biology: a textbook. John Wiley & Sons, 2016. Google Scholar
  33. Peter Kohl, Edmund J Crampin, TA Quinn, and Denis Noble. Systems biology: an approach. Clinical Pharmacology & Therapeutics, 88(1):25-33, 2010. Google Scholar
  34. Aditi Laddha and Santosh Vempala. Convergence of Gibbs Sampling: Coordinate Hit-and-Run Mixes Fast, 2020. URL: http://arxiv.org/abs/2009.11338.
  35. Yin Tat Lee and Santosh S. Vempala. Convergence rate of riemannian hamiltonian monte carlo and faster polytope volume computation. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 1115–1121, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3188745.3188774.
  36. László Lovász, Ravi Kannan, and Miklós Simonovits. Random walks and an O^*(n⁵) volume algorithm for convex bodies. Random Structures and Algorithms, 11:1-50, 1997. Google Scholar
  37. László Lovász and Santosh Vempala. Simulated annealing in convex bodies and an O^*(n⁴) volume algorithms. J. Computer & System Sciences, 72:392-417, 2006. Google Scholar
  38. Maximilian Lularevic, Andrew J Racher, Colin Jaques, and Alexandros Kiparissides. Improving the accuracy of flux balance analysis through the implementation of carbon availability constraints for intracellular reactions. Biotechnology and bioengineering, 116(9):2339-2352, 2019. Google Scholar
  39. Michael MacGillivray, Amy Ko, Emily Gruber, Miranda Sawyer, Eivind Almaas, and Allen Holder. Robust analysis of fluxes in genome-scale metabolic pathways. Scientific Reports, 7, December 2017. URL: https://doi.org/10.1038/s41598-017-00170-3.
  40. Daniel Machado, Sergej Andrejev, Melanie Tramontano, and Kiran Raosaheb Patil. Fast automated reconstruction of genome-scale metabolic models for microbial species and communities. Nucleic acids research, 46(15):7542-7553, 2018. Google Scholar
  41. Jens Maurer and Steven Watanabe. Boost random number library. Software, 2017. URL: https://www.boost.org/doc/libs/1_73_0/doc/html/boost_random.html.
  42. Hariharan Narayanan and Piyush Srivastava. On the mixing time of coordinate hit-and-run, 2020. URL: http://arxiv.org/abs/2009.14004.
  43. Denis Noble. The music of life: biology beyond genes. Oxford University Press, 2008. Google Scholar
  44. Alberto Noronha, Jennifer Modamio, Yohan Jarosz, Elisabeth Guerard, Nicolas Sompairac, German Preciat, Anna Dröfn Daníelsdóttir, Max Krecke, Diane Merten, Hulda S Haraldsdóttir, Almut Heinken, Laurent Heirendt, Stefanía Magnúsdóttir, Dmitry A Ravcheev, Swagatika Sahoo, Piotr Gawron, Lucia Friscioni, Beatriz Garcia, Mabel Prendergast, Alberto Puente, Mariana Rodrigues, Akansha Roy, Mouss Rouquaya, Luca Wiltgen, Alise Žagare, Elisabeth John, Maren Krueger, Inna Kuperstein, Andrei Zinovyev, Reinhard Schneider, Ronan M T Fleming, and Ines Thiele. The Virtual Metabolic Human database: integrating human and gut microbiome metabolism with nutrition and disease. Nucleic Acids Research, 47(D1):D614-D624, October 2018. URL: https://doi.org/10.1093/nar/gky992.
  45. Jeffrey D Orth, Ines Thiele, and Bernhard Ø. Palsson. What is flux balance analysis? Nature biotechnology, 28(3):245-248, 2010. Google Scholar
  46. Bernhard Ø. Palsson. Metabolic systems biology. FEBS letters, 583(24):3900-3904, 2009. Google Scholar
  47. Bernhard Ø. Palsson. Systems biology. Cambridge university press, 2015. Google Scholar
  48. Octavio Perez-Garcia, Gavin Lear, and Naresh Singhal. Metabolic network modeling of microbial interactions in natural and engineered environmental systems. Frontiers in microbiology, 7:673, 2016. Google Scholar
  49. Robert A. Quinn, Jose A. Navas-Molina, Embriette R. Hyde, Se Jin Song, Yoshiki Vázquez-Baeza, Greg Humphrey, James Gaffney, Jeremiah J. Minich, Alexey V. Melnik, Jakob Herschend, Jeff DeReus, Austin Durant, Rachel J. Dutton, Mahdieh Khosroheidari, Clifford Green, Ricardo da Silva, Pieter C. Dorrestein, and Rob Knight. From sample to multi-omics conclusions in under 48 hours. msystems 1: e00038-16. Crossref, Medline, 2016. Google Scholar
  50. Vivekananda Roy. Convergence Diagnostics for Markov Chain Monte Carlo. Annual Review of Statistics and Its Application, 7(1):387-412, 2020. URL: https://doi.org/10.1146/annurev-statistics-031219-041300.
  51. Pedro A. Saa and Lars K. Nielsen. ll-ACHRB: a scalable algorithm for sampling the feasible solution space of metabolic networks. Bioinform., 32(15):2330-2337, 2016. URL: https://doi.org/10.1093/bioinformatics/btw132.
  52. Jan Schellenberger and Bernhard Ø. Palsson. Use of randomized sampling for analysis of metabolic networks. Journal of biological chemistry, 284(9):5457-5461, 2009. Google Scholar
  53. John R Schramski, Anthony I Dell, John M Grady, Richard M Sibly, and James H Brown. Metabolic theory predicts whole-ecosystem properties. Proceedings of the National Academy of Sciences, 112(8):2617-2622, 2015. Google Scholar
  54. Siamak S. Shishvan, Andrea Vigliotti, and Vikram S. Deshpande. The homeostatic ensemble for cells. Biomechanics and Modeling in Mechanobiology, 17(6):1631-1662, 2018. Google Scholar
  55. Robert L. Smith. Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Operations Research, 32(6):1296-1308, 1984. Google Scholar
  56. Neil Swainston, Kieran Smallbone, Hooman Hefzi, Paul D. Dobson, Judy Brewer, Michael Hanscho, Daniel C. Zielinski, Kok Siong Ang, Natalie J. Gardiner, Jahir M. Gutierrez, Sarantos Kyriakopoulos, Meiyappan Lakshmanan, Shangzhong Li, Joanne K. Liu, Veronica S. Martínez, Camila A. Orellana, Lake-Ee Quek, Alex Thomas, Juergen Zanghellini, Nicole Borth, Dong-Yup Lee, Lars K. Nielsen, Douglas B. Kell, Nathan E. Lewis, and Pedro Mendes. Recon 2.2: from reconstruction to model of human metabolism. Metabolomics, 12(7):109, 2016. URL: https://doi.org/10.1007/s11306-016-1051-4.
  57. Ines Thiele and Bernhard Ø. Palsson. A protocol for generating a high-quality genome-scale metabolic reconstruction. Nature protocols, 5(1):93, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact