Home | About | Journals | Submit | Contact Us | Français |

**|**BMC Bioinformatics**|**v.11; 2010**|**PMC2963619

Formats

Article sections

- Abstract
- Background
- Implementation
- Results and Discussion
- Conclusions
- Availability and requirements
- Authors' contributions
- Supplementary Material
- References

Authors

Related links

BMC Bioinformatics. 2010; 11: 489.

Published online 2010 September 29. doi: 10.1186/1471-2105-11-489

PMCID: PMC2963619

Steinn Gudmundsson: si.ih@gnniets; Ines Thiele: si.ih@eleihti

Received 2010 May 26; Accepted 2010 September 29.

Copyright ©2010 Gudmundsson and Thiele; licensee BioMed Central Ltd.

This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

This article has been cited by other articles in PMC.

Flux variability analysis is often used to determine robustness of metabolic models in various simulation conditions. However, its use has been somehow limited by the long computation time compared to other constraint-based modeling methods.

We present an open source implementation of flux variability analysis called fastFVA. This efficient implementation makes large-scale flux variability analysis feasible and tractable allowing more complex biological questions regarding network flexibility and robustness to be addressed.

Networks involving thousands of biochemical reactions can be analyzed within seconds, greatly expanding the utility of flux variability analysis in systems biology.

Flux balance analysis (FBA) [1,2] is concerned with the following linear program (LP)

$$\begin{array}{ll}{\mathrm{max}}_{v}\hfill & {c}^{T}v\hfill \\ \text{subjectto}\hfill & Sv\text{\hspace{0.17em}}=\text{\hspace{0.17em}}0\hfill \\ \hfill & {v}_{l}\le \text{\hspace{0.17em}}v\text{\hspace{0.17em}}\le \text{\hspace{0.17em}}{v}_{u}\hfill \end{array}$$

(1)

where the matrix **S **is an *m *× *n stoichiometry *matrix with *m *metabolites and *n *reactions and **c **is the vector representing the linear objective function. The decision variables **v **represent *fluxes*, with **V ** * ^{n }*and vectors

Flux variability analysis (FVA) [3] is used to find the minimum and maximum flux for reactions in the network while maintaining some state of the network, e.g., supporting 90% of maximal possible biomass production rate.

Applications of FVA for molecular systems biology include, but are not limited to, the exploration of alternative optima of (1) [3], studying flux distributions under suboptimal growth [4], investigating network flexibility and network redundancy [5], optimization of process feed formulation for antibiotic production [6], and optimal strain design procedures as a pre-processing step [7,8].

Let **w **represent some biological objective such as biomass or ATP production. After solving (1) with **c **= **w**, FVA solves two optimization problems for each flux *v _{i }*of interest

$$\begin{array}{ll}{\text{max}}_{v}/{\mathrm{min}}_{v}\hfill & {v}_{i}\hfill \\ \text{subjectto}\hfill & Sv\text{\hspace{0.17em}}\text{=}\text{\hspace{0.17em}}0\hfill \\ \hfill & {w}^{T}v\text{\hspace{0.17em}}\ge \text{\hspace{0.17em}}\gamma {Z}_{0}\hfill \\ \hfill & {v}_{l}\text{\hspace{0.17em}}\le \text{\hspace{0.17em}}v\text{\hspace{0.17em}}\le \text{\hspace{0.17em}}{v}_{u}\hfill \end{array}$$

(2)

where *Z*_{0 }= **w**^{T}**v**_{0 }is an optimal solution to (1), *γ *is a parameter, which controls whether the analysis is done w.r.t. suboptimal network states (0 ≤ *γ <*1) or to the optimal state (*γ *= 1). Assuming that all *n *reactions are of interest, FVA requires the solution of 2*n *LPs. While FVA is clearly an embarrassingly parallel problem and is therefore ideally suited for computer clusters, this note focuses on how FVA can be run efficiently on a single CPU. A multi-CPU implementation of fastFVA can be done in the same way as for FVA, i.e., by distributing subsets of the *n *reactions to individual CPUs. It is expected to give almost linear speedup for sufficiently large problems.

A direct implementation of FVA iterates through all the *n *reactions and solves the two optimization problems in (2) from scratch each time by calling a specialized LP solver, such as GLPK [9] or CPLEX (IBM Inc.) At iteration *i*, *i *= 1, 2, ..., *n *all elements of **c **are zero except *c _{i }*= 1. Since the only difference between each iteration is a change in the objective function, i.e., the feasible region does not change, solving the LPs from scratch is wasteful. Each time a LP is solved, the solver has to spend some effort in finding a feasible solution. Once a feasible solution is found, the solver then proceeds to locate the optimum. The small changes in the objective function suggest that, on average, the optimum for iteration

Setup problem (1), denote it by *P*

Solve *P *from scratch to get **v**_{0 }and *Z*_{0}

Add the constraint **w**^{T}**v **≥ *γZ*_{0 }to *P*

`for `*i *= 1 to *n*

Let *c _{i }*= 1 and

Maximize *P*, starting from *v*_{i-}_{1}

to get **v*** _{i }*and

*maxFlux _{i }*=

Once all maximization problems have been solved, the minimization problems are solved in the same way, starting from **v**_{0 }= **v*** _{n}*.

An important difference between the various LP solvers available is their ability to exploit multiple core CPUs or multi-processor CPUs to increase performance. The GLPK solver, for example, is a single threaded application. When running on a quad-core machine with hyperthreading enabled, the CPU load is only at 12-13%. On multi-core machines, a significant speedup can often be achieved by simply running multiple instances of fastFVA, each working on a different subset of the *n *reactions.

The fastFVA package runs within the Matlab environment, which will facilitate the use of fastFVA by users less experienced in programming. In addition, many biochemical network models can be imported into Matlab using the Systems Biology Markup Language (SBML) and the COBRA toolbox [10].

The fastFVA code is written in C++ and is compiled as a Matlab EXecutable (MEX) file (additional file 1). Matlab's PARFOR command is used to exploit multi-core machines. Two different solvers are supported, the open-source GLPK package [9], and the industrial strength CPLEX solver from IBM.

We evaluated the performance of fastFVA on six biochemical network models ranging from approx. 650 up to 13,700 reactions (Table (Table1,1, additional file 2).

Four metabolic networks and two versions of a genome-scale network of the transcriptional and translational (tr/tr) machinery of *E. coli *were used for testing the fastFVA code (Table (Table1).1). The biomass reaction was used as an objective in the metabolic models, while the demand of ribosomal 50 S subunit was used as the objective in the tr/tr models. In all cases, flux distributions corresponding to at least 90% of optimal network functionality were sought.

The fastFVA code was tested on a DELL T1500 desktop computer with a 2.8 GHz quad core Intel i7 860 processor with hyperthreading enabled and Windows 7.

The running times are given in Table Table22 where fastFVA is compared to the direct implementation of FVA found in the COBRA toolbox [10]. The observed speedup is significant, ranging from 30 to 220 times faster for GLPK and from 20 to 120 times faster for CPLEX. The minimum and maximum flux values obtained with fastFVA were essentially identical to the values obtained with the direct approach (data not shown).

The fastFVA code can be used to compute the flux-spectrum [11], a variant of metabolic flux analysis, simply by setting *γ *= 0 in (2). The *α*-spectrum [12], which has been used to study flux distributions in terms of extreme pathways, can also be computed with fastFVA. In this case, the parameter *γ *in (2) is set to zero and the **S **matrix is replaced by a matrix **P **containing the extreme pathways as its columns.

With this efficient FVA tool in hand, new questions can be addressed to study the flexibility of biochemical reaction networks in different environmental and genetic conditions. It is now possible to design computational experiments requiring hundreds or even thousands of FVAs.

The fastFVA package is freely available at http://notendur.hi.is/ithiele/software/fastfva.html together with pre-compiled binaries for Linux and Microsoft Windows. The fastFVA code runs under Matlab and relies on third-party solvers to solve linear optimization problems. Two such solvers are supported, the open source GLPK [9] and the industrial strength CPLEX (IBM Inc.) The fastFVA code is written in C++ and is compiled as a Matlab EXecutable function (MEX). It is released under GNU LGPL.

IT conceived and designed the study. SG implemented fastFVA and carried out the experiments. Both authors wrote the manuscript and approved its final version.

**This file contains the C++ source code, the pre-compiled binaries, an example on how to use fastFVA and scripts for carrying out the experiments described above**.

Click here for file^{(51K, ZIP)}

**This file contains the six metabolic networks used in the experiments**.

Click here for file^{(2.5M, ZIP)}

We want to thank the authors of GLPK, GLPKMEX and CPLEXINT for making their code publicly available. We would like to thank the anonymous reviewers for their helpful comments. The authors are also grateful to Ronan M.T. Fleming for valuable discussions.

This study was supported by the Office of Science (ASCR), Department of Energy, under Award Number DE-SC00092009 ("Numerical Optimization Algorithms and Software for Systems Biology").

- Fell D, Small J. Fat synthesis in adipose tissue. An examination of stoichiometric constraints. Biochem J. 1986;238(3):781. [PubMed]
- Savinell J, Palsson B. Network analysis of intermediary metabolism using linear optimization. I. Development of mathematical formalism. J Theor Biol. 1992;154(4):421–454. doi: 10.1016/S0022-5193(05)80161-4. [PubMed] [Cross Ref]
- Mahadevan R, Schilling C. The effects of alternate optimal solutions in constraint-based genome-scale metabolic models. Metabolic engineering. 2003;5(4):264–276. doi: 10.1016/j.ymben.2003.09.002. [PubMed] [Cross Ref]
- Reed J, Palsson B. Genome-scale in silico models of
*E. coli*have multiple equivalent phenotypic states: assessment of correlated reaction subsets that comprise network states. Genome Research. 2004;14(9):1797. doi: 10.1101/gr.2546004. [PubMed] [Cross Ref] - Thiele I, Fleming R, Bordbar A, Schellenberger J, Palsson BO. Functional characterization of alternate optimal solutions of
*Escherichia coli*'s transcriptional and translational machinery. Biophysical Journal. 2010. in press . [PubMed] - Bushell M, Sequeira S, Khannapho C, Zhao H, Chater K, Butler M, Kierzek A, Avignone-Rossa C. The use of genome scale metabolic flux variability analysis for process feed formulation based on an investigation of the effects of the zwf mutation on antibiotic production in
*Streptomyces coelicolor*. Enzyme and Microbial Technology. 2006;39(6):1347–1353. doi: 10.1016/j.enzmictec.2006.06.011. [Cross Ref] - Pharkya P, Maranas C. An optimization framework for identifying reaction activation/inhibition or elimination candidates for overproduction in microbial systems. Metabolic engineering. 2006;8:1–13. doi: 10.1016/j.ymben.2005.08.003. [PubMed] [Cross Ref]
- Feist A, Zielinski D, Orth J, Schellenberger J, Herrgard M, Palsson B. Model-driven evaluation of the production potential for growth-coupled products of
*Escherichia coli*. Metabolic Engineering. 2009;12:173–186. doi: 10.1016/j.ymben.2009.10.003. [PMC free article] [PubMed] [Cross Ref] - Makhorin A. Glpk (gnu linear programming kit), version 4.42. http://www.gnu.org/software/glpk/
- Becker S, Feist A, Mo M, Hannum G, Palsson B, Herrgard M. Quantitative prediction of cellular metabolism with constraint-based models: the COBRA Toolbox. Nat Protoc. 2007;2(3):727–738. doi: 10.1038/nprot.2007.99. [PubMed] [Cross Ref]
- Llaneras F, Pico J. An interval approach for dealing with flux distributions and elementary modes activity patterns. Journal of theoretical biology. 2007;246(2):290–308. doi: 10.1016/j.jtbi.2006.12.029. [PubMed] [Cross Ref]
- Wiback S, Mahadevan R, Palsson B. Reconstructing metabolic flux vectors from extreme pathways: defining the
*α*-spectrum. Journal of theoretical biology. 2003;224(3):313–324. doi: 10.1016/S0022-5193(03)00168-1. [PubMed] [Cross Ref] - Zhang Y, Thiele I, Weekes D, Li Z, Jaroszewski L, Ginalski K, Deacon A, Wooley J, Lesley S, Wilson I, Palsson B, Osterman A, Godzik A. Three-Dimensional Structural View of the Central Metabolic Network of
*Thermotoga maritima*. Science. 2009;325(5947):1544. doi: 10.1126/science.1174671. [PMC free article] [PubMed] [Cross Ref] - Nogales J, Palsson B, Thiele I. A genome-scale metabolic reconstruction of
*Pseudomonas putida*KT 2440: iJN 746 as a cell factory. BMC Systems Biology. 2008;2:79. doi: 10.1186/1752-0509-2-79. [PMC free article] [PubMed] [Cross Ref] - Feist A, Henry C, Reed J, Krummenacker M, Joyce A, Karp P, Broadbelt L, Hatzimanikatis V, Palsson B. A genome-scale metabolic reconstruction for
*Escherichia coli*K-12 MG1655 that accounts for 1260 ORFs and thermodynamic information. Molecular systems biology. 2007. p. 3. [PMC free article] [PubMed] - Duarte N, Becker S, Jamshidi N, Thiele I, Mo M, Vo T, Srivas R, Palsson B. Global reconstruction of the human metabolic network based on genomic and bibliomic data. Proc Natl Acad Sci. 2007;104(6):1777. doi: 10.1073/pnas.0610772104. [PubMed] [Cross Ref]
- Thiele I, Jamshidi N, Fleming RMT, Palsson B. Genome-Scale Reconstruction of
*Escherichia coli*'s Transcriptional and Translational Machinery: A Knowledge Base, Its Mathematical Formulation, and Its Functional Characterization. PLoS Comput Biol. 2009;5(3):e1000312. doi: 10.1371/journal.pcbi.1000312. [PMC free article] [PubMed] [Cross Ref]

Articles from BMC Bioinformatics are provided here courtesy of **BioMed Central**

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |