Fast thermodynamically constrained flux variability analysis

Motivation: Flux variability analysis (FVA) is an important tool to further analy s e the results obtained by flux balance analysis (FBA) on genome-scale metabolic networks. For many constraint-based models , FVA identifies unboundedness of the optimal flux space. This reveals that optimal flux solutions with net flux through internal biochemical loops are feasible , which violates the second law of thermodynamics. Such unbounded fluxes may be eliminated by extending FVA with thermodynamic constraints.

Results: We present a new algorithm for efficient flux variability (and flux balance) analysis with thermodynamic constraints , suitable for analy s ing genome-scale metabolic networks. We first show that FBA with thermodynamic constraints is NP-hard. Then we derive a theoretical tractability result , which can be applied to metabolic networks in practice. We use this result to develop a new constraint programming algorithm Fast-tFVA for fast FVA with thermodynamic constraints (tFVA). Computational comparisons with previous methods demonstrate the efficiency of the new method. For tFVA , a speed-up of factor 30 – 300 is achieved. In an analysis of genome-scale metabolic networks in the BioModels database , we found that in 485 of 716 networks , additional irreversible or fixed reactions could be detected.

Availability and implementation: Fast-tFVA is written in C++ and published under GPL. It uses the open source software SCIP and libSBML. There also exists a Matlab interface for easy integration into Matlab. Fast-tFVA is available from page.mi.fu-berlin.de/arnem/fast-tfva.html.

Contact: [email protected] ; [email protected]

Supplementary information: Supplementary data are available at Bioinformatics online.