(182c) A Weighted Graph Algorithm for Identifying Dominant Metabolic Pathways

Metabolic pathway analysis identifies critical reactions in living organisms and plays a central role in synthetic biology. We present in this paper an algorithm, DOMINANT PATHWAY, for identifying the thermodynamically favored dominant pathway responsible for the production of a particular metabolite from a particular reactant. The metabolic network is represented as a graph. The problem is formulated to first identify the reaction-limiting capacity path between reactant and product based on thermodynamic information (Gibbs Free Energy Change of a reaction), and then augmenting the pathway with supplementary paths to identify a stoichiometrically balanced pathway. The algorithm's run time is O(|E| . lg |V|). When compared to the results obtained by Elementary Flux Mode analysis, the results on three test cases show that we are able to find the most thermodynamically favored path efficiently and effectively.