Unknown

Dataset Information

0

Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models.


ABSTRACT:

Motivation

Computation of steady-state flux solutions in large metabolic models is routinely performed using flux balance analysis based on a simple LP (Linear Programming) formulation. A minimal requirement for thermodynamic feasibility of the flux solution is the absence of internal loops, which are enforced using 'loopless constraints'. The resulting loopless flux problem is a substantially harder MILP (Mixed Integer Linear Programming) problem, which is computationally expensive for large metabolic models.

Results

We developed a pre-processing algorithm that significantly reduces the size of the original loopless problem into an easier and equivalent MILP problem. The pre-processing step employs a fast matrix sparsification algorithm-Fast- sparse null-space pursuit (SNP)-inspired by recent results on SNP. By finding a reduced feasible 'loop-law' matrix subject to known directionalities, Fast-SNP considerably improves the computational efficiency in several metabolic models running different loopless optimization problems. Furthermore, analysis of the topology encoded in the reduced loop matrix enabled identification of key directional constraints for the potential permanent elimination of infeasible loops in the underlying model. Overall, Fast-SNP is an effective and simple algorithm for efficient formulation of loop-law constraints, making loopless flux optimization feasible and numerically tractable at large scale.

Availability and implementation

Source code for MATLAB including examples is freely available for download at http://www.aibn.uq.edu.au/cssb-resources under Software. Optimization uses Gurobi, CPLEX or GLPK (the latter is included with the algorithm).

Contact

lars.nielsen@uq.edu.auSupplementary information: Supplementary data are available at Bioinformatics online.

SUBMITTER: Saa PA 

PROVIDER: S-EPMC5167067 | biostudies-literature | 2016 Dec

REPOSITORIES: biostudies-literature

altmetric image

Publications

Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models.

Saa Pedro A PA   Nielsen Lars K LK  

Bioinformatics (Oxford, England) 20160824 24


<h4>Motivation</h4>Computation of steady-state flux solutions in large metabolic models is routinely performed using flux balance analysis based on a simple LP (Linear Programming) formulation. A minimal requirement for thermodynamic feasibility of the flux solution is the absence of internal loops, which are enforced using 'loopless constraints'. The resulting loopless flux problem is a substantially harder MILP (Mixed Integer Linear Programming) problem, which is computationally expensive for  ...[more]

Similar Datasets

2015-03-21 | GSE67074 | GEO
| S-EPMC6559648 | biostudies-literature
| S-EPMC7468611 | biostudies-literature
| S-EPMC5999344 | biostudies-literature
| S-EPMC2962639 | biostudies-literature
| S-EPMC2754480 | biostudies-literature
| S-EPMC5518773 | biostudies-literature
| S-EPMC3488974 | biostudies-literature
| S-EPMC7516419 | biostudies-literature
| S-EPMC4032667 | biostudies-other