(430f) Linear Programming-Based Algorithm for Computing Metabolic Pathways From Genome-Scale Networks

Metabolic pathway analysis provides a useful means for exploring structural and functional properties of complex biological networks. While conventional numerical algorithms scale for a number of EMs running into the millions, genome-scale networks could involve significantly larger numbers, making the identification of EMs substantially more challenging. Alternatively, optimization-based algorithms have been suggested for selective extraction of metabolic pathways using mixed integer linear programming (MILP) (Lee et al. 2000) or integer programming (IP) (de Figueiredo et al. 2009; Rezola et al. 2011). While these methods raise prospects of identifying the full set of pathways for genome-scale networks, the process is still expensive because it involves additional integer variables to exclude previously found solutions. In this work, we present a novel optimization-based algorithm for efficient computation of metabolic pathways. The proposed method computes pathways usinglinear programming (LP) under integer-based constraints that are incorporated in a routine separated from the main optimization problem. Such a strategic partitioning of these two tasks (i.e., optimization solution and constraint design) into separate modules significantly reduces the memory requirement and enhances the computation speed by orders of magnitude. The developed algorithm may be useful in a wide range of applications including (i) metabolic pathway analysis, (ii) flux variability analysis, and (iii) network-based dynamic metabolic modeling (such as lumped hybrid cybernetic model (Song and Ramkrishna 2010; Song and Ramkrishna 2011).

References:

de 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(23):3158-3165.

Lee S, Phalakornkule C, Domach MM, Grossmann IE. 2000. Recursive MILP model for finding all the alternate optima in LP models for metabolic networks. Computers & Chemical Engineering 24(2-7):711-716.

Rezola A, de Figueiredo LF, Brock M, Pey J, Podhorski A, Wittmann C, Schuster S, Bockmayr A, Planes FJ. 2011. Exploring metabolic pathways in genome-scale networks via generating flux modes. Bioinformatics 27(4):534-540.

Song HS, Ramkrishna D. 2010. Prediction of Metabolic Function From Limited Data: Lumped Hybrid Cybernetic Modeling (L-HCM). Biotechnology and Bioengineering 106(2):271-284.

Song HS, Ramkrishna D. 2011. Cybernetic Models Based on Lumped Elementary Modes Accurately Predict Strain-Specific Metabolic Function. Biotechnology and Bioengineering 108(1):127-140.