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

Quek, Lake-Ee and Nielsen, Lars K (2014) A depth-first search algorithm to compute elementary flux modes by linear programming. BMC Systems Biology, 8 1: . doi:10.1186/s12918-014-0094-2

Author Quek, Lake-Ee
Nielsen, Lars K
Title A depth-first search algorithm to compute elementary flux modes by linear programming
Journal name BMC Systems Biology   Check publisher's open access policy
ISSN 1752-0509
Publication date 2014-07-30
Sub-type Article (original research)
DOI 10.1186/s12918-014-0094-2
Open Access Status DOI
Volume 8
Issue 1
Total pages 10
Place of publication London United Kingdom
Publisher BioMed Central
Collection year 2015
Language eng
Subject 1706 Computer Science Applications
2611 Modelling and Simulation
2604 Applied Mathematics
1315 Structural Biology
1312 Molecular Biology
Formatted abstract
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.

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.

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.
Keyword Elementary mode
Extreme pathway
Linear programming
Q-Index Code C1
Q-Index Status Confirmed Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: Official 2015 Collection
Australian Institute for Bioengineering and Nanotechnology Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 3 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 4 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Tue, 26 Aug 2014, 00:35:55 EST by System User on behalf of Aust Institute for Bioengineering & Nanotechnology