Abstract
We introduce a graph-theoretic formalism suitable for modeling biochemical networks marked by combinatorial complexity, such as signal-transduction systems, in which protein-protein interactions play a prominent role. This development extends earlier work by allowing for explicit representation of the connectivity of a protein complex. Within the formalism, typed attributed graphs are used to represent proteins and their functional components, complexes, conformations, and states of post-translational covalent modification. Graph transformation rules are used to represent protein-protein interactions and their effects. Each rule defines a generalized reaction, i.e., a class of potential reactions that are logically consistent with knowledge or assumptions about the represented biomolecular interaction. A model is specified by defining 1) molecular-entity graphs, which delimit the molecular entities and material components of a system and their possible states, 2) graph transformation rules, and 3) a seed set of graphs representing chemical species, such as the initial species present before introduction of a signal. A reaction network is generated iteratively through application of the graph transformation rules. The rules are first applied to the seed graphs and then to any and all new graphs that subsequently arise as a result of graph transformation. This procedure continues until no new graphs are generated or a specified termination condition is satisfied. The formalism supports the generation of a list of reactions in a system, which can be used to derive different types of physicochemical models, which can be simulated and analyzed in different ways. The processes of generating and simulating the network may be combined so that species are generated only as needed.
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
Aladjem, M.I., Pasa, S., Parodi, S., Weinstein, J.N., Pommier, Y., Kohn, K.W.: Molecular interaction maps—a diagrammatic graphical language for bioregulatory networks. In: Sci. STKE 2004, p. 8 (2004)
Andries, M., Engels, G., Habel, A., Hoffmann, B., Kreowski, H.J., Kuske, S., Plump, D., Schurr, A., Taentzer, A.: Graph transformation for specification and programming. Sci. Comput. Program. 34, 1–54 (1999)
Benkö, G., Flamm, C., Stadler, P.F.: A graph-based toy model of chemistry. J. Chem. Inf. Comput. Sci. 43, 1085–1093 (2003)
Blinov, M.L., Faeder, J.R., Goldstein, B., Hlavacek, W.S.: BioNetGen: software for rule-based modeling of signal transduction based on the interactions of molecular domains. Bioinformatics 20, 3289–3291 (2004)
Blinov, M.L., Faeder, J.R., Goldstein, B., Hlavacek, W.S.: A network model of early events in epidermal growth factor receptor signaling that accounts for combinatorial complexity. BioSystems (in press)
Borisov, N.M., Markevich, N.I., Hoek, J.B., Kholodenko, B.N.: Signaling through receptors and scaffolds: independent interactions reduce combinatorial complexity. Biophys. J. 89, 951–966 (2005)
Bray, D.: Molecular prodigality. Science 299, 1189–1190 (2003)
Conzelmann, H., Saez-Rodriguez, J., Sauter, T., Bullinger, E., Allgower, F., Gilles, E.D.: Reduction of mathematical models of signal transduction networks: simulation-based approach applied to EGF receptor signalling. Syst. Biol. 1, 159–169 (2004)
Danos, V., Laneve, C.: Graphs for core molecular biology. In: Priami, C. (ed.) CMSB 2003. LNCS, vol. 2602, pp. 34–46. Springer, Heidelberg (2003)
Danos, V., Laneve, C.: Formal molecular biology. Theor. Comput. Sci. 325, 69–110 (2004)
Dembo, M., Goldstein, B.: Theory of equilibrium binding of symmetric bivalent haptens to cell surface antibody: application to histamine release from basophils. J. Immunol. 121, 345–353 (1978)
Efroni, S., Harel, D., Cohen, I.R.: Towards rigorous comprehension of biological complexity: modeling, execution and visualization of thymic T cell maturation. Genome Res. 13, 2485–2497 (2003)
Ehrig, H., Heckel, R., Korff, M., Löwe, M., Ribeiro, L., Wagner, A., Corradini, A.: Algebraic approaches to graph transformation. Part II: single pushout approach and comparison with double pushout approach. In: Ehrig, H., Kreowski, H.-J., Montanari, U., Rozemberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformation, ch. 4, vol. 1, pp. 247–312. World Scientific, Singapore (1996)
Eker, S., Knapp, M., Laderoute, K., Lincoln, P., Meseguer, J., Sonmez, K.: Pathway logic: symbolic analysis of biological signaling. In: Pac. Symp. Biocomput., pp. 400–412 (2002)
Endy, D., Brent, R.: Modelling cellular behaviour. Nature 409, 391–395 (2001)
Faeder, J.R., Blinov, M.L., Hlavacek, W.S.: Graphical rule-based representation of signal-transduction networks. In: Proc. ACM Symp. Appl. Computing, pp. 133–140 (2005)
Faeder, J.R., Blinov, M.L., Hlavacek, W.S.: Rule-based modeling of biochemical networks. Complexity 10, 22–41 (2004)
Faeder, J.R., Blinov, M.L., Goldstein, B., Hlavacek, W.S.: Combinatorial complexity and dynamical restriction of network flows in signal transduction. Syst. Biol. 2, 5–15 (2005)
Faeder, J.R., Hlavacek, W.S., Reischl, I., Blinov, M.L., Metzger, H., Redondo, A., Wofsy, C., Goldstein, B.: Investigation of early events in FcεRI-mediated signaling using a detailed mathematical model. J. Immunol. 170, 3769–3781 (2003)
Fages, F., Soliman, S., Chabrier-Rivier, N.: Modelling and querying interaction networks in the biochemical abstract machine BIOCHAM. J. Biol. Phys. Chem. 4, 64–73 (2004)
Faulon, J.-L.: Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs. J. Chem. Inf. Comput. Sci. 38, 432–444 (1998)
Finney, A.: Developing SBML beyond level 2: proposals for development. In: Danos, V., Schachter, V. (eds.) CMSB 2004. LNCS (LNBI), vol. 3082, pp. 242–247. Springer, Heidelberg (2005)
Gillespie, D.T.: A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. J. Comput. Phys. 22, 403–434 (1976)
Gillespie, D.T.: Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem. 81, 2340–2361 (1977)
Goldstein, B., Faeder, J.R., Hlavacek, W.S., Blinov, M.L., Redondo, A., Wofsy, C.: Modeling the early signaling events mediated by FcεRI. Mol. Immunol. 38, 1213–1219 (2002)
Goldstein, B., Faeder, J.R., Hlavacek, W.S.: Mathematical and computational models of immune-receptor signalling. Nat. Rev. Immunol. 4, 445–456 (2004)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, San Francisco (1979)
Haugh, J.M., Schneider, I.C., Lewis, J.M.: On the cross-regulation of protein tyrosine phosphatases and receptor tyrosine kinases in intracellular signaling. J. Theor. Biol. 230, 119–132 (2004)
Hlavacek, W.S., Faeder, J.R., Blinov, M.L., Perelson, A.S., Goldstein, B.: The complexity of complexes in signal transduction. Biotechnol. Bioeng. 84, 783–794 (2003)
Hucka, M., Finney, A., et al.: The systems biology markup language (SBML): a medium for representation and exchange of biochemical network models. Bioinformatics 19, 524–531 (2003)
Hucka, M., Finney, A., et al.: Evolving a lingua franca and associated software infrastructure for computational systems biology: the Systems Biology Markup Language (SBML) project. Syst. Biol. 1, 41–53 (2004)
Kitano, H.: A graphical notation for biochemical networks. BioSilico 1, 169–176 (2003)
Klavins, E., Christ, R., Lipsky, D.: Graph grammars for self assembling robotic systems. In: Proc. IEEE Int. Conf. Rob. Autom., pp. 5293–5300 (2004)
Kohn, K.W.: Molecular interaction maps as information organizers and simulation guides. Chaos 11, 84–97 (2001)
Le Novère, N., Shimizu, T.S.: STOCHSIM: modelling of stochastic biomolecular processes. Bioinformatics 17, 575–576 (2001)
Li, Q., Dinner, A.R., Qi, S., Irvine, D.J., Huppa, J.B., Davis, M.M., Chakraborty, A.K.: CD4 enhances T cell sensitivity to antigen by coordinating Lck accumulation at the immunological synapse. Nat. Immunol. 5, 791–799 (2004)
Lok, L., Brent, R.: Automatic generation of cellular reaction networks with Moleculizer 1.0. Nat. Biotechnol. 23, 131–136 (2005)
Luks, E.M.: Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci. 25, 42–65 (1982)
McKay, B.D.: Practical graph isomorphism. Congressus Numerantium 30, 45–87 (1981)
Morton-Firth, C.J., Bray, D.: Predicting temporal fluctuations in an intracellular signalling pathway. J. Theor. Biol. 192, 117–128 (1998)
Pawson, T., Nash, P.: Assembly of cell regulatory systems through protein interaction domains. Science 300, 445–452 (2003)
Peri, S., et al.: Development of human protein reference database as an initial platform for approaching systems biology in humans. Genome Res. 13, 2363–2371 (2003)
Priami, C., Regev, A., Shapiro, E., Silverman, W.: Application of a stochastic name-passing calculus to representation and simulation of molecular processes. Inf. Process Lett. 80, 25–31 (2001)
Regev, A., Silverman, W., Shapiro, E.: Representation and simulation of biochemical processes using the π-calculus process algebra. In: Pac. Symp. Biocomput., pp. 459–470 (2001)
Rosello, R., Valiente, G.: Graph transformation in molecular biology. In: Kreowski, H.-J., Montanari, U., Orejas, F., Rozenberg, G., Taentzer, G. (eds.) Formal Methods in Software and Systems Modeling. LNCS, vol. 3393, pp. 116–133. Springer, Heidelberg (2005)
Shapiro, B.E., Levchenko, A., Meyerowitz, E.M., Wold, B.J., Mjolsness, E.D.: Cellerator: extending a computer algebra system to include biochemical arrows for signal transduction simulations. Bioinformatics 19, 677–678 (2003)
Shimizu, T.S., Aksenov, S.V., Bray, D.: A spatially extended stochastic model of the bacterial chemotaxis signalling pathway. J. Mol. Biol. 329, 291–309 (2003)
Talcott, C., Eker, S., Knapp, M., Lincoln, P., Laderoute, K.: Pathway logic modeling of protein functional domains in signal transduction. In: Pac. Symp. Biocomput., pp. 568–580 (2004)
Taentzer, G.: AGG: a graph transformation environment for modeling and validation of software. In: Pfaltz, J.L., Nagl, M., Böhlen, B. (eds.) AGTIVE 2003. LNCS, vol. 3062, pp. 446–453. Springer, Heidelberg (2004)
Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM 23, 31–42 (1976)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Blinov, M.L., Yang, J., Faeder, J.R., Hlavacek, W.S. (2006). Graph Theory for Rule-Based Modeling of Biochemical Networks. In: Priami, C., Ingólfsdóttir, A., Mishra, B., Riis Nielson, H. (eds) Transactions on Computational Systems Biology VII. Lecture Notes in Computer Science(), vol 4230. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11905455_5
Download citation
DOI: https://doi.org/10.1007/11905455_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-48837-8
Online ISBN: 978-3-540-48839-2
eBook Packages: Computer ScienceComputer Science (R0)