A depth-first search algorithm to compute elementary flux modes by linear programming

详细信息    查看全文

• 作者：Lake-Ee Quek (1)
  Lars K Nielsen (1)
  
  1. Australian Institute for Bioengineering and Nanotechnology ; The University of Queensland ; Queensland ; 4072 ; Australia
  
• 关键词：Elementary mode ; Extreme pathway ; Linear programming ; Rank ; Parallel ; Memory
• 刊名：BMC Systems Biology
• 出版年：2014
• 出版时间：December 2014
• 年：2014
• 卷：8
• 期：1
• 全文大小：1,083 KB
• 参考文献：1. Schuster, S, Fell, DA, Dandekar, T (2000) A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks. Nat Biotechnol 18: pp. 326-332 CrossRef
  2. Trinh, CT, Wlaschin, A, Srienc, F (2009) Elementary mode analysis: a useful metabolic pathway analysis tool for characterizing cellular metabolism. Appl Microbiol Biotechnol 81: pp. 813-826 CrossRef
  3. Song, HS, Ramkrishna, D (2009) Reduction of a set of elementary modes using yield analysis. Biotechnol Bioeng 102: pp. 554-568 CrossRef
  4. Trinh, CT, Srienc, F (2009) Metabolic engineering of Escherichia coli for efficient conversion of glycerol to ethanol. Appl Environ Microbiol 75: pp. 6696-6705 CrossRef
  5. Papin, JA, Price, ND, Wiback, SJ, Fell, DA, Palsson, BO (2003) Metabolic pathways in the post-genome era. Trends Biochem Sci 28: pp. 250-258 CrossRef
  6. Kamp, A, Schuster, S (2006) Metatool 5.0: fast and flexible elementary modes analysis. Bioinformatics 22: pp. 1930-1931 CrossRef
  7. Terzer, M, Stelling, J (2008) Large-scale computation of elementary flux modes with bit pattern trees. Bioinformatics 24: pp. 2229-2235 CrossRef
  8. Motzkin, TS, Raiffa, H, Thompson, GL, Thrall, RM The Double Description Method. In: Kuhn, HW, Tucker, AW eds. (1953) Contributions to the Theory of Games II, Vol. 8. Princeton University Press, New Jersey, pp. 51-73
  9. Wagner, C (2004) Nullspace approach to determine the elementary modes of chemical reaction systems. J Phys Chem B 108: pp. 2425-2431
  10. Machado, D, Soons, Z, Patil, KR, Ferreira, EC, Rocha, I (2012) Random sampling of elementary flux modes in large-scale metabolic networks. Bioinformatics 28: pp. i515-i521 CrossRef
  11. Acuna, V, Marchetti-Spaccamela, A, Sagot, MF, Stougie, L (2010) A note on the complexity of finding and enumerating elementary modes. Biosystems 99: pp. 210-214 CrossRef
  12. Jevremovic, D, Trinh, CT, Srienc, F, Sosa, CP, Boley, D (2011) Parallelization of nullspace algorithm for the computation of metabolic pathways. Parallel Comput 37: pp. 261-278 CrossRef
  13. Terzer, M, Stelling, J Parallel Extreme Ray and Pathway Computation. In: Wyrzykowski, R, Dongarra, J, Karczewski, K, Wasniewski, J, Wyrzykowski, R, Dongarra, J, Karczewski, K, Wasniewski, J eds. (2010) Parallel Processing and Applied Mathematics, Vol. 6068. Springer Berlin/Heidelberg, Berlin, pp. 300-309 CrossRef
  14. Gagneur, J, Klamt, S (2004) Computation of elementary modes: a unifying framework and the new binary approach. BMC Bioinformatics 5: pp. 175 CrossRef
  15. Hunt, KA, Folsom, JP, Taffs, RL, Carlson, RP (2014) Complete enumeration of elementary flux modes through scalable demand-based subnetwork definition. Bioinformatics 30: pp. 1569-1578 CrossRef
  16. Jevremovic, D, Boley, D, Sosa, CP (2011) Divide-and-Conquer Approach to the Parallel Computation of Elementary Flux Modes in Metabolic Networks. Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium. pp. 502-511 CrossRef
  17. Schwartz, JM, Kanehisa, M (2006) Quantitative elementary mode analysis of metabolic pathways: the example of yeast glycolysis. BMC Bioinformatics 7: pp. 186 CrossRef
  18. Kaleta, C, Figueiredo, LF, Behre, J, Schuster, S (2009) EFMEvolver: computing elementary flux modes in genome-scale metabolic networks. Lect Notes Informat P-157: pp. 179-189
  19. Gebauer, J, Schuster, S, Figueiredo, LF, Kaleta, C (2012) Detecting and investigating substrate cycles in a genome-scale human metabolic network. FEBS J 279: pp. 3192-3202 CrossRef
  20. Bohl, K, Figueiredo, LF, H盲dicke, O, Klamt, S, Kost, C, Schuster, S, Kaleta, C (2010) CASOP GS: Computing Intervention Strategies Targeted at Production Improvement in Genome-scale Metabolic Networks. 2010. pp. 71-80
  21. Figueiredo, LF, Podhorski, A, Rubio, A, Kaleta, C, Beasley, JE, Schuster, S, Planes, FJ (2009) Computing the shortest elementary flux modes in genome-scale metabolic networks. Bioinformatics 25: pp. 3158-3165 CrossRef
  22. Feist, AM, Henry, CS, Reed, JL, Krummenacker, M, Joyce, AR, Karp, PD, Broadbelt, LJ, Hatzimanikatis, V, Palsson, BO (2007) A genome-scale metabolic reconstruction for Escherichia coli K-12 MG1655 that accounts for 1260 ORFs and thermodynamic information. Mol Syst Biol 3: pp. 121 CrossRef
  23. Schilling, CH, Palsson, BO (1998) The underlying pathway structure of biochemical reaction networks. Proc Natl Acad Sci U S A 95: pp. 4193-4198 CrossRef
  24. Wiechert, W, Graaf, AA (1997) Bidirectional reaction steps in metabolic networks: I. Modeling and simulation of carbon isotope labeling experiments. Biotechnol Bioeng 55: pp. 101-117 CrossRef
  25. Urbanczik, R, Wagner, C (2005) An improved algorithm for stoichiometric network analysis: theory and applications. Bioinformatics 21: pp. 1203-1210 CrossRef
  26. Jevremovic, D, Trinh, CT, Srienc, F, Boley, D (2010) On algebraic properties of extreme pathways in metabolic networks. J Comput Biol 17: pp. 107-119 CrossRef
  27. Mahadevan, R, Schilling, CH (2003) The effects of alternate optimal solutions in constraint-based genome-scale metabolic models. Metab Eng 5: pp. 264-276 CrossRef
  28. Klamt, S, Kamp, A (2011) An application programming interface for CellNetAnalyzer. Biosystems 105: pp. 162-168 CrossRef
  29. Klamt, S, Gagneur, J, Kamp, A (2005) Algorithmic approaches for computing elementary modes in large biochemical reaction networks. Syst Biol (Stevenage) 152: pp. 249-255 CrossRef
  30. Jungreuthmayer, C, Ruckerbauer, DE, Zanghellini, J (2013) regEfmtool: speeding up elementary flux mode calculation using transcriptional regulatory rules in the form of three-state logic. Biosystems 113: pp. 37-39 CrossRef
  31. Jol, SJ, K眉mmel, A, Terzer, M, Stelling, J, Heinemann, M (2012) System-level insights into yeast metabolism by thermodynamic analysis of elementary flux modes. PLoS Comput Biol 8: pp. 1553-7358 CrossRef
  32. Boghigian, BA, Shi, H, Lee, K, Pfeifer, BA (2010) Utilizing elementary mode analysis, pathway thermodynamics, and a genetic algorithm for metabolic flux determination and optimal metabolic network design. BMC Syst Biol 4: pp. 49 CrossRef
  
• 刊物主题：Bioinformatics; Systems Biology; Simulation and Modeling; Computational Biology/Bioinformatics; Physiological, Cellular and Medical Topics; Algorithms;
• 出版者：BioMed Central
• ISSN：1752-0509

文摘

Background The decomposition of complex metabolic networks into elementary flux modes (EFMs) provides a useful framework for exploring reaction interactions systematically. Generating a complete set of EFMs for large-scale models, however, is near impossible. Even for moderately-sized models ( Results Based on an alternative elementarity test, we developed a depth-first search algorithm using linear programming (LP) to enumerate EFMs in an exhaustive fashion. Constraints can be introduced to directly generate a subset of EFMs satisfying the set of constraints. The depth-first search algorithm has a constant memory overhead. Using flux constraints, a large LP problem can be massively divided and parallelized into independent sub-jobs for deployment into computing clusters. Since the sub-jobs do not overlap, the approach scales to utilize all available computing nodes with minimal coordination overhead or memory limitations. Conclusions The speed of the algorithm was comparable to efmtool, a mainstream Double Description method, when enumerating all EFMs; the attrition power gained from performing flux feasibility tests offsets the increased computational demand of running an LP solver. Unlike the Double Description method, the algorithm enables accelerated enumeration of all EFMs satisfying a set of constraints.