Abstract
We propose a computational method for reconstructing metabolic networks. The method utilizes optimization techniques and graph traversal algorithms to discover a set of biochemical reactions that is most likely catalyzed by the enzymatic genes of the target organism. Unlike most existing computational methods for metabolic reconstruction, our method generates networks that are structurally consistent, or in other terms, gapless. As many analyses of metabolic networks, like flux balance analysis, require gapless networks as inputs, our network offers a more realistic basis for metabolic modelling than the existing automated reconstruction methods. It is easy to incorporate existing information, like knowledge about experimentally discovered metabolic reactions or metabolites into the process. Thus, our method can be used to assist in the manual curation of metabolic network models as it is able to suggest good candidate reactions for filling gaps in the existing network models. However, it is not necessary to assume any prior knowledge on composition of complete biochemical pathways in the network. We argue that this makes the method well-suited to analysis of organisms that might differ considerably from previously known organisms. We demonstrate the viability of our method by analysing the metabolic network of the well-known organism Escherichia coli.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
BMVis graph visualisation tool. Department of Computer Science, University of Helsinki, http://www.cs.helsinki.fi/group/biomine
Altschul, S.F., Madden, T.L., Schaffer, A.A., Zhang, J., Zhang, Z., Miller, W., Lipman, D.J.: Gapped blast and psi-blast: a new generation of protein database search programs. Nucleic Acids Research 25, 3389–3402 (1997)
Berkelaar, M., Eikland, K., Notebaert, P.: lp_solve: Open source (mixed-integer) linear programming system, Multi-platform, pure ANSI C / POSIX source code, Lex/Yacc based parsing. Version 5.1.0.0 dated 1 May 2004. GNU LGPL (Lesser General Public Licence) (2005), http://groups.yahoo.com/group/lp_solve
Blattner, F.R., Plunkett 3rd, G., Bloch, C.A., Perna, N.T., Burland, V., Riley, M., Collado-Vides, J., Glasner, J.D., Rode, C.K., Mayhew, G.F., Gregor, J., Davis, N.W., Kirkpatrick, H.A., Goeden, M.A., Rose, D.J., Mau, B., Shao, Y.: The complete genome sequence of escherichia coli k-12. Science 277, 1453–1474 (1997)
Burgard, A.P., Nikolaev, E.V., Schilling, C.H., Maranas, C.D.: Flux coupling analysis of genome-scale metabolic network reconstructions. Genome Research 14(2), 301–312 (2004)
Caspi, R., Foerster, H., Fulcher, C.A., Hopkinson, R., Ingraham, J., Kaipa, P., Krummenacker, M., Paley, S., Pick, J., Rhee, S.Y., Tissier, C., Zhang, P., Karp, P.D.: Metacyc: A multiorganism database of metabolic pathways and enzymes. Nucleic Acids Research 516, D511–D516 (2006)
Chen, L., Vitkup, D.: Predicting genes for orphan metabolic activities using phylogenetic profiles. Genome Biology 7(R17), 1777–1782 (2006)
The UniProt Consortium. The universal protein resource (uniprot). Nucleic Acids Research 35, D193–D197 (2007)
Cordwell, S.J.: Microbial genomes and ”missing” enzymes: redefining biochemical pathways. Arch Microbiol 172, 269–279 (1999)
Csete, M., Doyle, J.: Bow ties, metabolism and disease. TRENDS in Biotechnology 22(9), 446–450 (2004)
Duarte, N., Becker, S., Jamshidi, N., Thiele, I., Mo, M., Vo, T., Srivas, R., Palsson, B.: Global reconstruction of the human metabolic network based on genomic and bibliomic data. Proceedings of National Academy of Science, USA 104(6), 1777–1782 (2007)
Duarte, N., Herrgård, M., Palsson, B.: Reconstruction and validation of Saccharomyces cerevisiae iND750, a fully compartmentalized genome-scale metabolic model. Genome Research 14(7), 1298–1309 (2004)
Edwards, J., Palsson, B.: The Escherichia coli MG1655 in silico metabolic genotype: its definition, characteristics, and capabilities. Proceedings of National Academy of Science, USA 97(10), 5528–5533 (2000)
Riley, M., et al.: Escherichia coli k-12: a cooperatively developed annotation snapshot. Nucleic Acids Res. 34(1), 1–9 (2006)
Caspi, R., et al.: The metacyc database of metabolic pathways and enzymes and the biocyc collection of pathway/genome databases. Nucleic Acids Research 36(Database issue), 623–631 (2008)
Förster, J., Famili, I., Fu, P., Palsson, B., Nielsen, J.: Genome-scale reconstruction of the Saccharomyces cerevisiae metabolic network. Genome Research 13(2), 244–253 (2003)
Francke, C., Siezen, R.J., Teusink, B.: Reconstructing the metabolic network of a bacterium from its genome. Trends Microbiol 13(11), 550–558 (2005)
Galperin, M., Koonin, E.: Who’s your neighbor? new computational approaches for functional genomics. Nat. Biotechnol. 18, 609–613 (2000)
Green, M., Karp, P.D.: A Bayesian method for identifying missing enzymes in predicted metabolic pathway databases. BMC Bioinformatics 5(76) (2004)
Hatzimanikatis, V., Li, C., Ionita, J.A., Henry, C.S., Jankowski, M.D., Broadbelt, L.J.: Exploring the diversity of complex metabolic networks. Bioinformatics 21(8) (2005)
Herrgård, M., Fong, S., Palsson, B.: Identification of genome-scale metabolic network models using experimentally measured flux profiles. PLoS Computational Biology 2(7), 72 (2006)
IUBMB. Enzyme Nomenclature. Academic Press (1992)
Karp, P., Paley, S., Romero, P.: The pathway tools software. Bioinformatics 232, S225–S232 (2002)
Keseler, I.M., Collado-Vides, J., Gama-Castro, S., Ingraham, J., Paley, S., Paulsen, I.T., Peralta-Gil, M., Karp, P.D.: EcoCyc: A comprehensive database resource for Escherichia coli. Nucleic Acids Research 337, D334–D337 (2005)
Kharchenko, P., Chen, L., Freund, Y., Vitkup, D., Church, G.M.: Identifying metabolic enzymes with multiple types of association evidence. BMC Bioinformatics 7(177) (2006)
Kharchenko, P., Church, G.M., Vitkup, D.: Filling gaps in a metabolic network using expression information. Bioinformatics 185, I178–I185 (2004)
Kim, P.-J., Lee, D.-Y., Kim, T., Lee, K., Jeong, H., Lee, S., Park, S.: Metabolite essentiality elucidates robustness of escherichia coli metabolism. Proceedings of National Academy of Science, USA 104(34), 13638–13642 (2007)
Kumar, V., Dasika, M., Maranas, C.: Optimization based automated curation of metabolic reconstructions. BMC Bioinformatics 8(212), 13638–13642 (2007)
Marcotte, E.: Computational genetics: finding protein function by nonhomology methods. Curr. Opin. Struct. Biol. 10, 359–365 (2000)
McGuire, A., Hughes, J., Church, G.: Conservation of DNA regulatory motifs and discovery of new motifs in microbial genomes. Genome Res. 10, 744–757 (2000)
Osterman, A., Overbeek, R.: Missing genes in metabolic pathways: a comparative genomics approach. Current Opinion in Chemical Biology 7, 238–251 (2003)
Pharkya, P., Maranas, C.D.: An optimization framework for identifying reaction activation/inhibition or elimination candidates for overproduction in microbial systems. Metabolic Engineering 8(1), 1–13 (2006)
Pitkänen, E., Rantanen, A., Rousu, J., Ukkonen, E.: Finding feasible pathways in metabolic networks. In: Bozanis, P., Houstis, E.N. (eds.) PCI 2005. LNCS, vol. 3746, pp. 123–133. Springer, Heidelberg (2005)
Resendis-Antonio, O., Reed, J., Encarnación, S., Collado-Vides, J., Palsson, B.: Metabolic reconstruction and modeling of nitrogen fixation in Rhizobium etli. PLoS Computational Biology 3(10), 13638–13642 (2007)
Schilling, C.H., Letscher, D., Palsson, B.: Theory for the systemic definition of metabolic pathways and their use in interpreting metabolic function from a pathway-oriented perspective. Journal of Theoretical Biology 203(3), 228–248 (2003)
Schuster, S., Fell, D.A., Dandekar, T.: A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic network. Nature Biotechnology 18, 326–332 (2000)
Stelling, J., Klamt, S., Bettenbrock, K., Schuster, S., Gilles, E.D.: Metabolic network structure determines key aspects of functionality and regulation. Nature 420, 190–193 (2002)
van Rossum, G., Drake Jr., F.L.: An Introduction to Python. Network Theory Ltd. (2006)
Wolf, Y., Rogozin, I., Kondrashov, A., Koonin, E.: Genome alignment, evolution of prokaryotic genome organization, and prediction of gene function using genomic context. Genome Res. 11, 356–372 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pitkänen, E., Rantanen, A., Rousu, J., Ukkonen, E. (2008). A Computational Method for Reconstructing Gapless Metabolic Networks. In: Elloumi, M., Küng, J., Linial, M., Murphy, R.F., Schneider, K., Toma, C. (eds) Bioinformatics Research and Development. BIRD 2008. Communications in Computer and Information Science, vol 13. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70600-7_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-70600-7_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70598-7
Online ISBN: 978-3-540-70600-7
eBook Packages: Computer ScienceComputer Science (R0)