gEFM: An Algorithm for Computing Elementary Flux Modes Using Graph Traversal

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Ehsan UllahSoha Hassoun

Abstract

Computational methods to engineer cellular metabolism promise to play a critical role in producing pharmaceutical, repairing defective genes, destroying cancer cells, and generating biofuels. Elementary Flux Mode (EFM) analysis is one such powerful technique that has elucidated cell growth and regulation, predicted product yield, and analyzed network robustness. EFM analysis, however, is a computationally daunting task because it requires the enumeration of all independent and stoichiometrically balanced pathways within a cellular network. We present in this paper an EFM enumeration algorithm, termed graphical EFM or gEFM. The algorithm is based on graph traversal, an approach previously assumed unsuitable for enumerating EFMs. The approach is derived from a pathway synthesis method proposed by Mavrovouniotis et al. The algorithm is described and proved correct. We apply gEFM to several networks and report runtimes in comparison with other EFM computation tools. We show how gEFM benefits from network compression. Like other EFM computational techniques, gEFM is sensitive to constraint ordering; however, we are able to demonstrate that knowledge of the underlying network structure leads to better constraint ordering. gEFM is sho...Continue Reading

References

Nov 15, 2002·Nature·Jörg StellingErnst Dieter Gilles
Jan 14, 2004·Genome Research·Anthony P BurgardCostas D Maranas
Jan 22, 2004·Bioinformatics·Steffen Klamt, Ernst Dieter Gilles
Mar 31, 2004·Biotechnology and Bioengineering·Ross Carlson, Friedrich Srienc
Nov 6, 2004·BMC Bioinformatics·Julien Gagneur, Steffen Klamt
Mar 2, 2005·Applied Microbiology and Biotechnology·Natarajan VijayasankaranFriedrich Srienc
Sep 1, 1953·Proceedings of the National Academy of Sciences of the United States of America·T S Motzkin, O Taussky
May 30, 2006·Bioinformatics·Axel von Kamp, Stefan Schuster
Feb 13, 2007·Journal of Theoretical Biology·F Llaneras, J Picó
Apr 22, 2008·Applied and Environmental Microbiology·Cong T TrinhFriedrich Srienc
Dec 20, 1990·Biotechnology and Bioengineering·M L MavrovouniotisG Stephanopoulos
Aug 30, 2008·Bio Systems·Vicente AcuñaLeen Stougie
Jan 1, 2009·Bioinformatics·Luis F de FigueiredoDavid A Fell
Jan 9, 2009·BMC Systems Biology·Nanette R Boyle, John A Morgan
Oct 17, 2009·Metabolic Engineering·Lake-Ee QuekLars K Nielsen
Dec 8, 2009·Bio Systems·Vicente AcuñaLeen Stougie
Sep 14, 2010·Wiley Interdisciplinary Reviews. Systems Biology and Medicine·Marco TerzerJörg Stelling
Oct 12, 2010·Metabolic Engineering·Ryan P Nolan, Kyongbum Lee
Jun 7, 2011·BMC Systems Biology·Kuhn IpDesmond S Lun
Sep 3, 2011·Science·Warren C RuderJames J Collins
Mar 15, 2012·PLoS Computational Biology·Stefan J JolMatthias Heinemann
May 31, 2012·Algorithms for Molecular Biology : AMB·Sayed-Amir MarashiAlexander Bockmayr
Sep 11, 2012·Bioinformatics·Daniel MachadoIsabel Rocha
Nov 23, 2013·BMC Systems Biology·Mona YousofshahiSoha Hassoun
Sep 12, 2015·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Laszlo David, Alexander Bockmayr
Dec 17, 2015·IEEE/ACM Transactions on Computational Biology and Bioinformatics·Ehsan UllahSoha Hassoun

❮ Previous
Next ❯

Citations

Nov 21, 2019·Briefings in Bioinformatics·Ehsan UllahSoha Hassoun
Jul 11, 2020·Computational Biology and Chemistry·Mona ArabzadehSayed-Amir Marashi
Jun 2, 2018·Bio Systems·Yosef BedasoHerbert M Sauro

❮ Previous
Next ❯

Related Concepts

Related Feeds

Biofuels (ASM)

Biofuels are produced through contemporary processes from biomass rather than geological processes involved in fossil fuel formation. Examples include biodiesel, green diesel, biogas, etc. Discover the latest research on biofuels in this feed.

Antiparasitics

Antiparasitics are medications which are indicated for the treatment of parasitic diseases. Discover the latest research on antiparasitics here.

Cancer Metabolism

In order for cancer cells to maintain rapid, uncontrolled cell proliferation, they must acquire a source of energy. Cancer cells acquire metabolic energy from their surrounding environment and utilize the host cell nutrients to do so. Here is the latest research on cancer metabolism.