In flux balance analysis of metabolic networks, reaction rates and optimal pathways are ascertained by solving a linear program, in which the growth rate is maximized subject to mass-balance constraints, and for which extracellular conditions represent parameters. However, for most large, genome-scale metabolic networks of practical interest, the resulting parametric problem has multiple and highly degenerate optimal solutions, which are computationally challenging to handle.

In An Improved Multi-parametric Programming Algorithm for Flux Balance Analysis of Metabolic Networks (click here for free access), an algorithm based on active-set methods is introduced to overcome these computational difficulties. Degeneracy and multiplicity are handled, respectively, by introducing generalized inverses and auxiliary objective functions into the formulation of the optimality conditions. These improvements are especially effective for metabolic networks because their stoichiometry matrices are generally sparse; thus, fast and efficient algorithms from sparse linear algebra can be leveraged to compute generalized inverses and null-space bases. The authors illustrate the application of the algorithm by studying a reduced metabolic model of Corynebacterium glutamicum and a genome-scale model of Escherichia coli, demonstrating how the resulting critical regions can be associated with optimal metabolic modes and discussing the physical relevance of optimal pathways arising from various auxiliary objective functions. Achieving more than fivefold improvement in computational speed over existing multi-parametric programming tools, the proposed algorithm proves promising in handling genome-scale metabolic models.