An improved multi-parametric programming algorithm for flux balance analysis of metabolic networks
From MaRDI portal
Publication:1670104
DOI10.1007/S10957-018-1281-XzbMATH Open1394.90422arXiv1802.02567OpenAlexW2962995278MaRDI QIDQ1670104FDOQ1670104
Authors: Amir Akbari, Paul I. Barton 
Publication date: 4 September 2018
Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)
Abstract: Flux balance analysis has proven an effective tool for analyzing metabolic networks. In flux balance analysis, reaction rates and optimal pathways are ascertained by solving a linear program, in which the growth rate is maximized subject to mass-balance constraints. A variety of cell functions in response to environmental stimuli can be quantified using flux balance analysis by parameterizing the linear program with respect to extracellular conditions. 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. An improved multi-parametric programming algorithm based on active-set methods is introduced in this paper 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. We illustrate the application of our algorithm to flux balance analysis of metabolic networks by studying a reduced metabolic model of Corynebacterium glutamicum and a genome-scale model of Escherichia coli. We then demonstrate how the critical regions resulting from these studies can be associated with optimal metabolic modes and discuss the physical relevance of optimal pathways arising from various auxiliary objective functions. Achieving more than five-fold improvement in computational speed over existing multi-parametric programming tools, the proposed algorithm proves promising in handling genome-scale metabolic models.
Full work available at URL: https://arxiv.org/abs/1802.02567
Recommendations
- On dynamically generating relevant elementary flux modes in a metabolic network using optimization
- Capturing the essence of a metabolic network: a flux balance analysis approach
- The Compact Kernel of a Metabolic Flux Balance Solution Space
- Algorithms to Study Large Metabolic Network Dynamics
- Dynamic optimization of metabolic networks coupled with gene expression
- A new constraint-based description of the steady-state flux cone of metabolic networks
- An inverse problem framework for dynamic metabolic resource allocation problems in systems biology
Quadratic programming (90C20) Linear programming (90C05) Large-scale problems in mathematical programming (90C06)
Cites Work
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Title not available (Why is that?)
- Title not available (Why is that?)
- Convex optimization theory.
- Generalized inverses. Theory and applications.
- Title not available (Why is that?)
- Model predictive control based on linear programming - the explicit solution
- Linear and integer programming: Theory and practice.
- Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations
- Lipschitz Continuity of Solutions of Linear Inequalities, Programs and Complementarity Problems
- The explicit linear quadratic regulator for constrained systems
- An algorithm for multi-parametric quadratic programming and explicit MPC solutions
- Efficient solution of ordinary differential equations with a parametric lexicographic linear program embedded
- An algorithm for the solution of multiparametric mixed integer linear programming problems
- Equivalent weights for lexicographic multi-objective programs: Characterizations and computations
- Continuous selection and unique polyhedral representation of solutions to convex parametric quadratic programs
- On the facet-to-facet property of solutions to convex parametric quadratic programs
- Preemptive and nonpreemptive multi-objective programming: Relationships and counterexamples
- Multiparametric Linear Programming
- Geometric algorithm for multiparametric linear programming
- On the uniqueness of solutions to linear programs
- The Existence of a Short Sequence of Admissible Pivots to an Optimal Basis in LP and LCP
- Nonlinear Perturbation of Linear Programs
- Accurate Symmetric Indefinite Linear Equation Solvers
- Lexicographic perturbation for multiparametric linear programming with applications to control
- Minimal representation of convex polyhedral sets
- Convexity recognition of the union of polyhedra
- On the Computation of Null Spaces of Sparse Rectangular Matrices
- An Explicit Solution of a Special Class of Linear Programming Problems
- Balinski-Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces
Cited In (13)
- Enumeration and Cartesian product decomposition of alternate optimal fluxes in cellular metabolism
- A space exploration algorithm for multiparametric programming via Delaunay triangulation
- Parameter estimation for metabolic networks with two stage Bregman regularization homotopy inversion algorithm
- The exact solution of multiparametric quadratically constrained quadratic programming problems
- Flux balance analysis: a geometric perspective
- A simplex approach to solving robust metabolic models with low-dimensional uncertainty
- A novel parallel combinatorial algorithm for multiparametric programming
- Computational method for inferring objective function of glycerol metabolism in Klebsiella pneumoniae
- Mixed-integer minimax dynamic optimization for structure identification of glycerol metabolic network
- Nonlinear multi-objective flux balance analysis of the Warburg Effect
- Parallelization of nullspace algorithm for the computation of metabolic pathways
- Capturing the essence of a metabolic network: a flux balance analysis approach
- On dynamically generating relevant elementary flux modes in a metabolic network using optimization
Uses Software
This page was built for publication: An improved multi-parametric programming algorithm for flux balance analysis of metabolic networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1670104)
