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...

Descripción completa

Detalles Bibliográficos
Autores principales: Saa, Pedro A., Nielsen, Lars K.
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