Graphical rule-based representation of signal-transduction networks

ABSTRACT

The process by which a cell senses and responds to its environment, as in signal transduction, is often mediated by a network of protein-protein interactions, in which proteins combine to form complexes and undergo post-translational modifications, which regulate their enzymatic and binding activities. A typical signaling protein contains multiple sites of protein interaction and modification and may contain catalytic domains. As a result, interactions of signaling proteins have the potential to generate a combinatorially large number of complexes and modified states, and representing signal-transduction networks can be challenging. Representation, in the form of a diagram or model, usually involves a tradeoff between comprehensibility and precision: comprehensible representations tend to be ambiguous or incomplete, whereas precise representations, such as a long list of chemical species and reactions in a network, tend to be incomprehensible. Here, we develop conventions for representing signal-transduction networks that are both comprehensible and precise. Labeled nodes represent components of proteins and their states, and edges represent bonds between components. Binding and enzymatic reactions are described by reaction rules, in which left graphs define the properties of reactants and right graphs define the products that result from transformations of reactants. The reaction rules can be evaluated to derive a mathematical model.

REFERENCES

• 1: T. Hunter. Signaling---2000 and beyond. Cell 100:113--127, 2000.
• 2: T. Pawson and P. Nash. Assembly of cell regulatory systems through protein interaction domains. Science 300:445--452, 2003.
• 3: M. Ptashne and A. Gann. Genes & Signals. Cold Spring Harbor Laboratory Press, Cold Spring Harbor, New York, 2002.
• 4: D. Bray. Molecular prodigality. Science 299:1189--1190, 2003.
• 5: W. S. Hlavacek, J. R. Faeder, M. L. Blinov, A. S. Perelson, and B. Goldstein. The complexity of complexes in signal transduction. Biotechnol. Bioeng. 84:783--794, 2003.
• 6: J. J. Tyson, K. C. Chen, and B. Novak. Sniffers, buzzers, toggles and blinkers: dynamics of regulatory and signaling pathways in the cell. Curr. Opin. Cell Biol. 15:221--231, 2003.
• 7: H. S. Wiley, S. Y. Shvartsman, and D. A. Lauffenburger. Computational modeling of the EGF-receptor system: a paradigm for systems biology. Trends Cell Biol. 13:43--50, 2003.
• 8: B. Goldstein, J. R. Faeder, and W. S. Hlavacek. Mathematical and computational models of immune-receptor signalling. Nat. Rev. Immunol. 4:445--456, 2004.
• 9: M. Hucka, A. Finney, H. M. Sauro, H. Bolouri, J. C. Doyle, H. Kitano, et al. The systems biology markup language (SBML): a medium for representation and exchange of biochemical network models. Bioinformatics 19:524--531, 2003.
• 10: K. W. Kohn. Molecular interaction maps as information organizers and simulation guides. Choos 11:84--97, 2001.
• 11: R. Maimon and S. Browning. Diagrammatic notation and computational structure of gene networks. In Proceedings of the Second International Conference on Systems Biology (T.-M. Yi, M. Hucka, M. Morohashi, and H. Kitano, eds.), pages 311--317, Omnipress, Madison, WI, 2001.
• 12: Kitano, H. A graphical notation for biochemical networks. Biosilico 1(5):169--176, November 2003
• 13: M. I. Aladjem, S. Pasa, S. Parodi, J. N. Weinstein, Y. Pommier, and K. W. Kohn. Molecular interaction maps---diagrammatic graphical language for bioregulatory networks. Sci. STKE 2004(222):pe8, March 2004.
• 14: B. Goldstein, J. R. Faeder, W. S. Hlavacek, M. L. Blinov, A. Redondo, and C. Wofsy. Modeling the early signaling events mediated by FceRI. Mol. Immunol. 38:1213--1219, 2002.
• 15: J. R. Faeder, W. S. Hlavacek, I. Reischl, M. L. Blinov, H. Metzger, A. Redondo, C. Wofsy, and B. Goldstein. Investigation of early events in FceRI-mediated signaling using a detailed mathematical model. J. Immunol. 170:3769--3781, 2003.
• 16: M. L. Blinov, J. R. Faeder, B. Goldstein, and W. S. Hlavacek. BioNetGen: software for rule-based modeling of signal transduction based on the interactions of molecular domains. Bioinformatics (in press) doi:10.1093/bioinformatics/bth378, June 2004.
• 17: James R. Faeder , Michael L. Blinov , Byron Goldstein , William S. Hlavacek, Rule-based modeling of biochemical networks: Research Articles, Complexity, v.10 n.4, p.22-41, March 2005 [doi>10.1002/cplx.v10:4]
• 18: J. R. Ullmann, An Algorithm for Subgraph Isomorphism, Journal of the ACM (JACM), v.23 n.1, p.31-42, Jan. 1976 [doi>10.1145/321921.321925]
• 19: Heiko Dorr, Efficient Graph Rewriting and Its Implementation, Springer-Verlag New York, Inc., Secaucus, NJ, 1995
• 20: B. D. McKay. Practical graph isomorphism. Congressus Numerantium, 30:45--87, 1981. Also see http://cs.anu.edu. au/~bdm/nauty/
• 21: J.-L. Faulon and A. G. Sault. Stochastic generator of chemical structure. 3. Reaction network generation. J. Chem. Inf. Comput. Sci. 41:894--908, 2001.
• 22: J. R. Faeder, M. L. Blinov, B. Goldstein, and W. S. Hlavacek. Combinatorial complexity and dynamical restriction of network flows in signal transduction. arXiv:q-bio.MN/0411021, submitted to Syst. Biol.
• 23: H. Conzelmann, J. Saez-Rodriguez, T. Sauter, E. Bullinger, F. Allgöwer, and E. D. Gilles. Reduction of mathematical models of signal transduction networks: simulation-based approach applied to EGF receptor signalling. Syst. Biol. 1:159--169.
• 24: M. Dembo and B. Goldstein. Theory of equilibrium binding of symmetric bivalent haptens to cell surface antibody: application to histamine release from basophils. J. Immunol. 121:345--353, 1978.
• 25: R. G. Posner, C. Wofsy, and B. Goldstein. The kinetics of the bivalent ligand-bivalent receptor aggregation: ring formation and the breakdown of the equivalent site approximation. Math. Biosci. 126:171--190, 1995
• 26: J.-L. Faulon. Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial time for molecular graphs. J. Chem. Inf. Comput. Sci. 38:432--444, 1998.
• 27: G. Benkö, C. Flamm, and P. F. Stadler. A graph-based toy model of chemistry. J. Chem. Inf. Comput. Sci. 43:1085--1093, 2003.
• 28: E. Klavins, R. Ghrist, and D. Lipsky. Graph grammars for self-assembling robotic systems. In Proceedings of the 2004 IEEE International Conference on Robotics and Automation5:5293--5300, 2004.
• 29: A. Regev and E. Shapiro. The π-calculus as an abstraction for biomolecular systems. Nat. Comp. Ser. pp. 219--266, 2004.
• 30: Vincent Danos , Cosimo Laneve, Formal molecular biology, Theoretical Computer Science, v.325 n.1, p.69-110, 28 September 2004 [doi>10.1016/j.tcs.2004.03.065]
• 31: C. Talcott, S. Eker, M. Knapp, P. Lincoln, and K. Laderoute. Pathway logic modeling of protein functional domains in signal transduction. Pac. Symp. Biocomput. pp. 568--580, 2004
• 32: B. R. Franza. From play to laws: language in biology. Sci. STKE pe9, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES

Keywords:
biological systems modeling, graph isomorphism, graph rewriting, protein interactions, signal transduction