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

Area of Science:

• Systems Biology
• Metabolic Engineering
• Computational Biology

Background:

• Decomposing metabolic networks into elementary flux modes (EFMs) aids in understanding reaction interactions.
• Generating all EFMs for large models is computationally prohibitive with existing methods like the Double Description method.
• Current approaches demand significant processor and memory resources, limiting scalability.

Purpose of the Study:

• To develop a novel, efficient algorithm for enumerating elementary flux modes (EFMs).
• To enable constraint-based generation of specific EFMs.
• To overcome the computational limitations of existing EFM enumeration techniques.

Main Methods:

• Developed a depth-first search algorithm incorporating an alternative elementarity test and linear programming (LP).
• Implemented constraint-based enumeration for targeted EFM generation.
• Designed the algorithm for constant memory overhead and parallelization across computing clusters.

Main Results:

• The novel algorithm achieves exhaustive EFM enumeration with constant memory usage.
• It allows direct generation of EFMs satisfying specific flux constraints.
• The approach demonstrates significant scalability for large-scale metabolic models.

Conclusions:

• The new algorithm's speed is comparable to existing Double Description methods for full EFM enumeration.
• It accelerates the enumeration of constraint-specific EFMs, a key advantage over traditional methods.
• The algorithm's parallelizable nature and constant memory overhead overcome scalability issues.