Decomposing biochemical networks into elementary flux modes using graph traversal

Ehsan Ullah, Calvin Hopkins, Shuchin Aeron, Soha Hassoun

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Citations (Scopus)

Abstract

Elementary Flux Mode (EFM) analysis is a fundamental network decomposition technique used for cellular pathway analysis in Systems Biology and Metabolic Engineering. EFM analysis has been utilized to examine robustness, regulation and microbial stress responses, to increase product yield, and to assess plant FItness and agricultural productivity. An EFM is a thermodynamically feasible path operating at steady state in a biochemical network, and is independent of other EFMs in the sense that it cannot be generated as a non-negative linear combination of other EFMs. We present in this paper a pathway analysis algorithm, termed graphical EFM or gEFM, based on graph traversal. Graph theoretical approaches were previously assumed to be less competitive than techniques based on the double-description method, a computational technique used for enumerating the extreme rays of a pointed cone. Importantly, we show that a practical graph-based traversal approach for computing EFMs is competitive with existing techniques. Applied to several biochemical networks, we show runtime speedups in the range of 2.5× to 31× when compared to the state-of-the-art tool (EFMTool).

Original languageEnglish
Title of host publication2013 ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013
Pages211-218
Number of pages8
DOIs
Publication statusPublished - 2013
Externally publishedYes
Event2013 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013 - Wshington, DC, United States
Duration: 22 Sept 201325 Sept 2013

Publication series

Name2013 ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013

Conference

Conference2013 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013
Country/TerritoryUnited States
CityWshington, DC
Period22/09/1325/09/13

Keywords

  • Biochemical networks
  • EFMS
  • Elementary flux modes
  • Elementary modes
  • Flux modes
  • Graph algorithms
  • Metabolic networks
  • Network analysis
  • Pathway analysis

Fingerprint

Dive into the research topics of 'Decomposing biochemical networks into elementary flux modes using graph traversal'. Together they form a unique fingerprint.

Cite this