TY - GEN
T1 - Decomposing biochemical networks into elementary flux modes using graph traversal
AU - Ullah, Ehsan
AU - Hopkins, Calvin
AU - Aeron, Shuchin
AU - Hassoun, Soha
PY - 2013
Y1 - 2013
N2 - 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).
AB - 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).
KW - Biochemical networks
KW - EFMS
KW - Elementary flux modes
KW - Elementary modes
KW - Flux modes
KW - Graph algorithms
KW - Metabolic networks
KW - Network analysis
KW - Pathway analysis
UR - http://www.scopus.com/inward/record.url?scp=84888181515&partnerID=8YFLogxK
U2 - 10.1145/2506583.2506620
DO - 10.1145/2506583.2506620
M3 - Conference contribution
AN - SCOPUS:84888181515
SN - 9781450324342
T3 - 2013 ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013
SP - 211
EP - 218
BT - 2013 ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013
T2 - 2013 4th ACM Conference on Bioinformatics, Computational Biology and Biomedical Informatics, ACM-BCB 2013
Y2 - 22 September 2013 through 25 September 2013
ER -