(200h) Computing Elementary Flux Modes Using a Graph-Based Approach

Elementary flux mode analysis is a network decomposition technique now recognized as a cornerstone in metabolic engineering for cellular pathway analysis with applications to analyze robustness, regulation, microbial stress responses, to increase product yield, and to assess plant fitness and agricultural productivity.   An Elementary flux is a thermodynamically feasible route that operates in steady-state, and is independent in the sense that it cannot be generated as a non-negative linear combination of other elementary flux modes.  We present an algorithm, graphical EFM or gEFM, to compute elementary flux modes.  The algorithm is based on graph traversal, an approach that was previously assumed to be less competitive than other EFM computing techniques.   The basic underlying idea in gEFM is inspired from the work of Mavrovouniotis et al. on the synthesis of metabolic pathways from a given substrate(s) to a given product(s) (Mavrovouniotis et a., 1990).  Conceptually, the Mavrovouniotis approach iteratively satisfies a set of stoichiometric constraints, and transforms an initial set of reactions (one-step pathways) into a final set of pathways that satisfy all the constraints.  The number of generated pathways is dependent on the order in which metabolites are processed, and not all generated pathways are EFMs.   In our work, a dependence check is applied after processing each metabolite identifies the EFMs.   Importantly, we show that a practical implementation of gEFM when applied to several test cases is able to achieve significant speedups over MetaTool 5.1, and the single-threaded version of EFMTool.