Cargando…
Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models
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...
Autores principales: | , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Oxford University Press
2016
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5167067/ https://www.ncbi.nlm.nih.gov/pubmed/27559155 http://dx.doi.org/10.1093/bioinformatics/btw555 |
_version_ | 1782483130443104256 |
---|---|
author | Saa, Pedro A. Nielsen, Lars K. |
author_facet | Saa, Pedro A. Nielsen, Lars K. |
author_sort | Saa, Pedro A. |
collection | PubMed |
description | 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.au Supplementary information: Supplementary data are available at Bioinformatics online. |
format | Online Article Text |
id | pubmed-5167067 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2016 |
publisher | Oxford University Press |
record_format | MEDLINE/PubMed |
spelling | pubmed-51670672016-12-20 Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models Saa, Pedro A. Nielsen, Lars K. Bioinformatics Original Papers 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.au Supplementary information: Supplementary data are available at Bioinformatics online. Oxford University Press 2016-12-15 2016-08-24 /pmc/articles/PMC5167067/ /pubmed/27559155 http://dx.doi.org/10.1093/bioinformatics/btw555 Text en © The Author 2016. Published by Oxford University Press. http://creativecommons.org/licenses/by-nc/4.0/ This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/), which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited. For commercial re-use, please contact journals.permissions@oup.com |
spellingShingle | Original Papers Saa, Pedro A. Nielsen, Lars K. Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models |
title | Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models |
title_full | Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models |
title_fullStr | Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models |
title_full_unstemmed | Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models |
title_short | Fast-SNP: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models |
title_sort | fast-snp: a fast matrix pre-processing algorithm for efficient loopless flux optimization of metabolic models |
topic | Original Papers |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5167067/ https://www.ncbi.nlm.nih.gov/pubmed/27559155 http://dx.doi.org/10.1093/bioinformatics/btw555 |
work_keys_str_mv | AT saapedroa fastsnpafastmatrixpreprocessingalgorithmforefficientlooplessfluxoptimizationofmetabolicmodels AT nielsenlarsk fastsnpafastmatrixpreprocessingalgorithmforefficientlooplessfluxoptimizationofmetabolicmodels |