Dataset Information

A depth-first search algorithm to compute elementary flux modes by linear programming.

ABSTRACT:

Background

The decomposition of complex metabolic networks into elementary flux modes (EFMs) provides a useful framework for exploring reaction interactions systematically. Generating a complete set of EFMs for large-scale models, however, is near impossible. Even for moderately-sized models (<400 reactions), existing approaches based on the Double Description method must iterate through a large number of combinatorial candidates, thus imposing an immense processor and memory demand.

Results

Based on an alternative elementarity test, we developed a depth-first search algorithm using linear programming (LP) to enumerate EFMs in an exhaustive fashion. Constraints can be introduced to directly generate a subset of EFMs satisfying the set of constraints. The depth-first search algorithm has a constant memory overhead. Using flux constraints, a large LP problem can be massively divided and parallelized into independent sub-jobs for deployment into computing clusters. Since the sub-jobs do not overlap, the approach scales to utilize all available computing nodes with minimal coordination overhead or memory limitations.

Conclusions

The speed of the algorithm was comparable to efmtool, a mainstream Double Description method, when enumerating all EFMs; the attrition power gained from performing flux feasibility tests offsets the increased computational demand of running an LP solver. Unlike the Double Description method, the algorithm enables accelerated enumeration of all EFMs satisfying a set of constraints.

SUBMITTER: Quek LE

PROVIDER: S-EPMC4236763 | biostudies-literature | 2014 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

A depth-first search algorithm to compute elementary flux modes by linear programming.

Quek Lake-Ee LE Nielsen Lars K LK

BMC systems biology 20140730

<h4>Background</h4>The decomposition of complex metabolic networks into elementary flux modes (EFMs) provides a useful framework for exploring reaction interactions systematically. Generating a complete set of EFMs for large-scale models, however, is near impossible. Even for moderately-sized models (<400 reactions), existing approaches based on the Double Description method must iterate through a large number of combinatorial candidates, thus imposing an immense processor and memory demand.<h4> ...[more]

PMID: 25074068

Similar Datasets

Project description:Background(13)C metabolic flux analysis is one of the pertinent ways to compare two or more physiological states. From a more theoretical standpoint, the structural properties of metabolic networks can be analysed to explore feasible metabolic behaviours and to define the boundaries of steady state flux distributions. Elementary flux mode analysis is one of the most efficient methods for performing this analysis. In this context, recent approaches have tended to compare experimental flux measurements with topological network analysis.ResultsMetabolic networks describing the main pathways of central carbon metabolism were set up for a bacteria species (Corynebacterium glutamicum) and a plant species (Brassica napus) for which experimental flux maps were available. The structural properties of each network were then studied using the concept of elementary flux modes. To do this, coefficients of flux efficiency were calculated for each reaction within the networks by using selected sets of elementary flux modes. Then the relative differences - reflecting the change of substrate i.e. a sugar source for C. glutamicum and a nitrogen source for B. napus - of both flux efficiency and flux measured experimentally were compared. For both organisms, there is a clear relationship between these parameters, thus indicating that the network structure described by the elementary flux modes had captured a significant part of the metabolic activity in both biological systems. In B. napus, the extension of the elementary flux mode analysis to an enlarged metabolic network still resulted in a clear relationship between the change in the coefficients and that of the measured fluxes. Nevertheless, the limitations of the method to fit some particular fluxes are discussed.ConclusionThis consistency between EFM analysis and experimental flux measurements, validated on two metabolic systems allows us to conclude that elementary flux mode analysis could be a useful tool to complement (13)C metabolic flux analysis, by allowing the prediction of changes in internal fluxes before carbon labelling experiments.

Dataset Information

A depth-first search algorithm to compute elementary flux modes by linear programming.

Background

Results

Conclusions

Publications

A depth-first search algorithm to compute elementary flux modes by linear programming.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure