A Weighted Graph Algorithm for Identifying Dominant Metabolic Pathways

Tuesday, November 10, 2009: 9:10 AM
Bayou D (Gaylord Opryland Hotel)

Ehsan Ullah, Computer Science, Tufts University, Medford, MA
Mark A. Walker, Chemical and Biological Engineering, Tufts University, Medford, MA
Kyongbum Lee, Chemical and Biological Engineering, Tufts University, Medford, MA
Soha Hassoun, Computer Science, Tufts University, Medford, MA

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.
Extended Abstract: File Not Uploaded
See more of this Session: Advances in Metabolic Engineering I
See more of this Group/Topical: Food, Pharmaceutical & Bioengineering Division