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

BMC Systems Biology

Lars K Nielsen¹  Lake-Ee Quek¹ 

[1] Australian Institute for Bioengineering and Nanotechnology, The University of Queensland, Queensland 4072, Australia

关键词: Memory;    Parallel;    Rank;    Linear programming;    Extreme pathway;    Elementary mode;   

Others  :  1159581
DOI  :  10.1186/s12918-014-0094-2

 received in 2014-02-24, accepted in 2014-07-24,  发布年份 2014

【 摘 要 】

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 (<400 reactions), existing approaches based on the Double Description method must iterate through a large number of combinatorial candidates, thus imposing an immense processor and memory demand.

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.

【 授权许可】

   
2014 Quek and Nielsen

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

【 参考文献 】

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