Graph Transformation in Molecular Biology | SpringerLink
Skip to main content
Springer Nature Link
Log in

Graph Transformation in Molecular Biology

  • Chapter
Formal Methods in Software and Systems Modeling

Part of the book series: Lecture Notes in Computer Science ((LNPSE,volume 3393))

Abstract

In the beginning, one of the main fields of application of graph transformation was biology, and more specifically morphology. Later, however, it was like if the biological applications had been left aside by the graph transformation community, just to be moved back into the mainstream these very last years with a new interest in molecular biology. In this paper, we review several fields of application of graph grammars in molecular biology, including: the modelling of higher-dimensional structures of biomolecules, the description of biochemical reactions, and the study of biochemical pathways.

This work has been partially supported by the Spanish CICYT, project MAVERISH (TIC2001-2476-C03-01) and by the Spanish DGES and the EU program FEDER, project BFM2003-00771 ALBIOM.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abe, N., Mamitsuka, H.: Predicting protein secondary structure using stochastic tree grammars. Machine learning 29, 275–301 (1997)

    Article  MATH  Google Scholar 

  2. Beck, M., Benkö, G., Eble, C.F., Müller, S., Stadler, P.: Graph grammars as models for the evolution of developmental pathways. In: Schaub, H., Detje, F., Brüggemann, U. (eds.) The Logic of Artificial Life: Abstracting and Synthesizing the Principles of Living Systems, pp. 8–15. IOS Press, Amsterdam (2004)

    Google Scholar 

  3. Benkö, G., Flamm, C., Stadler, P.F.: A graph-based toy model of chemistry. Journal of Chemical Information and Computer Sciences 43, 1085–1093 (2003)

    Google Scholar 

  4. Benkö, G., Flamm, C., Stadler, P.F.: Multi-phase artificial chemistry. In: Schaub, H., Detje, F., Brüggemann, U. (eds.) The Logic of Artificial Life: Abstracting and Synthesizing the Principles of Living Systems, pp. 16–22. IOS Press, Amsterdam (2004)

    Google Scholar 

  5. Benkö, G., Flamm, C., Stadler, P.F.: Generic properties of chemical networks: Artificial chemistry based on graph rewriting. In: Banzhaf, W., Ziegler, J., Christaller, T., Dittrich, P., Kim, J.T. (eds.) ECAL 2003. LNCS (LNAI), vol. 2801, pp. 10–19. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  6. Bower, J.M., Bolouri, H.: Computational modeling of genetic and biochemical networks. MIT Press, Cambridge (2001)

    Google Scholar 

  7. Brendel, V., Busse, H.G.: Genome structure described by formal languages. Nucleic Acid Research 12, 2561–2568 (1984)

    Article  Google Scholar 

  8. Cardelli, L.: Brane calculi. In: Proc. Workshop Concurrent Methods in Molecular Biology. Electronic Notes in Theoretical Computer Science. Elsevier, Amsterdam (2004) (to appear)

    Google Scholar 

  9. Cayley, A.: On the mathematical theory of isomers. Philosophical Magazine 47, 444–446 (1874)

    Google Scholar 

  10. Chan, H.S., Dill, K.A.: Compact polymers. Macromolecules 22, 4559–4573 (1989)

    Article  Google Scholar 

  11. Corradini, A., Montanari, U., Rossi, F., Ehrig, H., Heckel, R., Löwe, M.: Algebraic approaches to graph transformation. Part I: Basic concepts and double pushout approach. In: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation. Foundations, vol. 1, pp. 163–246. World Scientific, Singapore (1997)

    Google Scholar 

  12. Culik II, K., Lindenmayer, A.: Parallel rewriting on graphs and multidimensional development. Int. Journ. of General Systems 3, 53–66 (1976)

    Article  MathSciNet  Google Scholar 

  13. Curti, M., Degano, P., Baldari, C.: Causal π-calculus for biochemical modelling. In: Priami, C. (ed.) CMSB 2003. LNCS, vol. 2602, pp. 21–33. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  14. Danos, V., Krivine, J.: Formal molecular biology done in CCS. In: Proc. Workshop Concurrent Methods in Molecular Biology. Electronic Notes in Theoretical Computer Science. Elsevier, Amsterdam (2004) (to appear)

    Google Scholar 

  15. Danos, V., Laneve, C.: Graphs for core molecular biology. In: Priami, C. (ed.) CMSB 2003. LNCS, vol. 2602, pp. 34–46. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  16. Danos, V., Laneve, C.: Core formal molecular biology. In: Degano, P. (ed.) ESOP 2003. LNCS, vol. 2618, pp. 302–318. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  17. Danos, V., Laneve, C.: Formal molecular biology. Theoretical Computer Science 325, 69–110 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  18. Deville, Y., Gilbert, D., van Helden, J., Wodak, S.J.: An overview of data models for the analysis of biochemical pathways. Briefings in Bioinformatics 4, 246–259 (2003)

    Article  Google Scholar 

  19. Fringuelli, F., Taticchi, A.: The Diels-Alder Reaction: Selected Practical Methods. John Wiley & Sons, Chichester (2002)

    Google Scholar 

  20. Dittrich, P., Ziegler, J., Banzhaff, W.: Artificial chemistries—a review. Artificial life 7, 225–275 (2001)

    Article  Google Scholar 

  21. Durbin, R., Krogh., A., Mitchison, G., Eddy, S.: Biological sequence analysis: Probabilistic models of proteins and nucleic acids. Cambridge Univ. Press, Cambridge (1998)

    Book  MATH  Google Scholar 

  22. Ehrenfeucht, A., Harju, T., Petre, I., Prescott, D.M., Rosenberg, G.: Computation in Living Cells: Gene Assembly in Ciliates. Natural computing series. Springer, Berlin (2004)

    MATH  Google Scholar 

  23. 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: Rozenberg, G. (ed.) Handbook of Graph Grammars and Computing by Graph Transformation. Foundations, vol. 1, pp. 247–312. World Scientific, Singapore (1997)

    Google Scholar 

  24. Ehrig, H., Mahr, B.: Fundamentals of algebraic specification I: Equations and initial semantics. Springer, Heidelberg (1985)

    MATH  Google Scholar 

  25. Eker, S., Knapp, M., Laderoute, K., Lincoln, P., Meseguer, J., Sonmez, K.: Pathway logic: Symbolic analisys of biological signalling. In: Pacific symposium on Biocomputing 2001, pp. 400–412. World Scientific, Singapore (2001)

    Google Scholar 

  26. Fan, L.T., Bertók, B., Friedler, F.: A graph-theoretic method to identify candidate mechanisms for deriving the rate law of a catalytic reaction. Computers & Chemistry 26, 265–292 (2002)

    Article  Google Scholar 

  27. Félix, L., Rosselló, F., Valiente, G.: Artificial chemistries and metabolic pathways. In: Messeguer, X., Valiente, G. (eds.) Proc. 5th Annual Spanish Bioinformatics Conference, Barcelona, Technical University of Catalonia, pp. 56–59 (2004)

    Google Scholar 

  28. Flamm, C., Fontana, W., Hofacker, I., Schuster, P.: Kinetic folding of RNA at elementary step resolution. RNA 6, 325–338 (2000)

    Article  Google Scholar 

  29. Fontana, W.: Algorithmic chemistry. In: Artificial Life II. Santa Fe Institute Studies in the Sciences of Complexity, vol. 47, pp. 159–210. Addison-Wesley, Reading (1992)

    Google Scholar 

  30. Fujita, S.: Description of organic reactions based on imaginary transition structures. Part 1-5. Journal of Chemical Information and Computer Sciences 26, 205–242 (1986)

    Google Scholar 

  31. Fujita, S.: Computer-Oriented Representation of Organic Reactions. Yoshioka Shoten, Kyoto (2001)

    Google Scholar 

  32. Fujita, S.: Description of organic reactions based on imaginary transition structures. Part 6-9. Journal of Chemical Information and Computer Sciences 27, 99–120 (1987)

    Google Scholar 

  33. Gernert, D.: Graph grammars as an analytical tool in physics and biology. Biosystems 43, 179–187 (1997)

    Article  Google Scholar 

  34. Goss, P., Peccoud, J.: Quantitative modelling of stochastic systems in molecular biology using stochastic Petri nets. Proc. Nat. Acad. Sc. 95, 6750–6755 (1998)

    Article  Google Scholar 

  35. Heckel, R., Lajios, G., Menge, S.: Stochastic graph transformation systems. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 210–225. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  36. Hofacker, I., Fontana, W., Stadler, P., Bonhoeffer, L., Tacker, M., Schuster, P.: Fast folding and comparison of RNA secondary structures. Monatsh. Chem. 125, 167–188 (1994)

    Article  Google Scholar 

  37. Kanehisa, M., Goto, S.: KEGG: Kyoto encyclopedia of genes and genomes. Nucleic Acids Research 28, 27–30 (2000)

    Article  Google Scholar 

  38. Kister, A., Magarshak, Y., Malinsky, J.: The theoretical analysis of the process of RNA molecule self-assembly. BioSystems 30, 31–48 (1993)

    Article  Google Scholar 

  39. Kitano, H.: Computational systems biology. Nature 420, 206–210 (2002)

    Article  Google Scholar 

  40. Lesk, A.M.: Systematic representation of protein folding patterns. J. Mol. Graph. 13, 159–164 (1995)

    Article  Google Scholar 

  41. Mayoh, B.: On patterns and graphs (1995) (preprint)

    Google Scholar 

  42. Mayoh, B.: Multidimensional Lindenmayer organisms. In: L-systems. LNCS, vol. 15, pp. 302–326. Springer, Heidelberg (1974)

    Google Scholar 

  43. McAdams, H., Arkin, A.: It’s a noisy business! Genetic regulation at the nanomolar scale. Trends in Genetics 15, 65–69 (1999)

    Article  Google Scholar 

  44. McCaskill, J., Niemann, U.: Graph replacement chemistry for DNA processing. In: Condon, A., Rozenberg, G. (eds.) DNA 2000. LNCS, vol. 2054, pp. 103–116. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  45. Michal, G. (ed.): Biological Pathways: An Atlas of Biochemistry and Molecular Biology. John Wiley & Sons, New York (1999)

    Google Scholar 

  46. Polanski, O.: Graphs in quantum chemistry. MATCH 1, 183–195 (1975)

    Google Scholar 

  47. Priami, C. (ed.): Proc. 1st Int. Workshop Computational Methods in Systems Biology. LNCS, vol. 2602. Springer, Heidelberg (2003)

    Google Scholar 

  48. Przytycka, T., Srinivasan, T., Rose, G.: Recursive domains in proteins. Protein Science 11, 409–417 (2002)

    Article  Google Scholar 

  49. Regev, A., Silverman, W., Shapiro, E.: Representation and simulation of biochemical processes using the π- calculus process algebra. In: Pacific symposium on Biocomputing 2001, pp. 459–470. World Scientific, Singapore (2001)

    Google Scholar 

  50. Regev, A., Shapiro, E.: Cells as computation. Nature 419, 343 (2002)

    Article  Google Scholar 

  51. Reidys, C., Stadler, P.F.: Bio-molecular shapes and algebraic structures. Computers & Chemistry 20, 85–94 (1996)

    Article  Google Scholar 

  52. Richardson, J.: β-sheet topology and the relatedness of proteins. Nature 268, 495–500 (1977)

    Article  Google Scholar 

  53. Rivas, E., Eddy, S.R.: The language of RNA: a formal grammar that includes pseudoknots. Bioinformatics 16, 334–340 (2000)

    Article  Google Scholar 

  54. Rosselló, F., Valiente, G.: Chemical graphs, chemical reaction graphs, and chemical graph transformation. In: Proc. 2nd Int. Workshop Graph-Based Tools. Electronic Notes in Theoretical Computer Science. Elsevier, Amsterdam (2004) (to appear)

    Google Scholar 

  55. Rosselló, F., Valiente, G.: Analysis of metabolic pathways by graph transformation. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 70–82. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  56. Sakakibara, Y., Brown, M., Hughey, R., Mian, I., Sjolander, K., Underwood, R., Haussler, D.: Stochastic context-free grammars for tRNA modeling. Nucleic Acids Research 22, 5112–5128 (1994)

    Article  Google Scholar 

  57. Schultz, J., Milpetz, F., Bork, P., Ponting, C.: SMART, a simple molecular architecture research tool. Proc. Nat. Acad. Sc. 95, 5857–5864 (1998)

    Article  Google Scholar 

  58. Searls, D.: The computational linguistics of biological sequences. In: Artificial Intelligence and Molecular Biology, pp. 47–120. AAAI Press, Menlo Park (1993)

    Google Scholar 

  59. Searls, D.: Formal language and biological macromolecules. In: Mathematical Support for Molecular Biology. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 47, pp. 128–141. AMS (1999)

    Google Scholar 

  60. Searls, D.: The language of genes. Nature 420, 211–217 (2002)

    Article  Google Scholar 

  61. Seo, H., Lee, D.Y., Park, S., Fan, L.T., Shafie, S., Bertók, B., Friedler, F.: Graphtheoretical identification of pathways for biochemical reactions. Biotechnology Letters 23, 1551–1557 (2001)

    Article  Google Scholar 

  62. Speroni, P.: Artificial chemistries. Bull. EATCS 76, 128–141 (2002)

    MATH  Google Scholar 

  63. Tomita, K., Kurokawa, H., Murata, S.: Graph automata: natural expression of self reproduction. Physica D 171, 197–210 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  64. Waterman, M.S., Smith, T.F.: RNA secondary structure: a complete mathematical analysis. Math. Biosci. 42, 257–266 (1978)

    Article  MATH  Google Scholar 

  65. Weininger, D.: SMILES, a chemical language and information system. 1. Introduction to methodology and encoding rules. Journal of Chemical Information and Computer Sciences 28, 31–36 (1988)

    Google Scholar 

  66. Weininger, D., Weininger, A., Weininger, J.L.: SMILES. 2. Algorithm for generation of unique SMILES notation. Journal of Chemical Information and Computer Sciences 29, 97–101 (1989)

    Google Scholar 

  67. Weininger, D.: SMILES. 3. DEPICT. Graphical depiction of chemical structures. Journal of Chemical Information and Computer Sciences 30, 237–243 (1990)

    Google Scholar 

  68. Westhead, D., Slidel, T., Flores, T., Thornton, J.: Protein structural topology: automated analysis and diagrammatic representation. Protein Science 8, 897–904 (1999)

    Article  Google Scholar 

  69. Yadav, M.K., Kelley, B.P., Silverman, S.M.: The potential of a chemical graph transformation system. In: Ehrig, H., Engels, G., Parisi-Presicce, F., Rozenberg, G. (eds.) ICGT 2004. LNCS, vol. 3256, pp. 83–95. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  70. Zevedei-Oancea, I., Schuster, S.: Topological analysis of metabolic networks based on Petri net theory. Silico Biology 3, 323–345 (2003)

    Google Scholar 

  71. Zuker, M., Sankoff, D.: RNA secondary structures and their prediction. Bull. Math. Biol. 46, 591–621 (1984)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, Research Institute of Health Science (IUNICS), University of the Balearic Islands, Palma de Mallorca, Spain

    Francesc Rosselló

  2. Department of Software, Technical University of Catalonia, Barcelona, Spain

    Gabriel Valiente

Authors
  1. Francesc Rosselló
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gabriel Valiente
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, University of Bremen, P.O. Box 33 04 40, 28334, Bremen, Germany

    Hans-Jörg Kreowski

  2. Dipartimento di Informatica, Università di Pisa,  

    Ugo Montanari

  3. Dpto de L.S.I., Universitat Politècnica de Catalunya, Campus Nord, Mòdul Omega, Jordi Girona 1-3, 08034, Barcelona, Spain

    Fernando Orejas

  4. Leiden Center of Advanced Computer Science (LIACS), Leiden University, Niels Bohrweg 1, 2333, Leiden, CA, The Netherlands

    Grzegorz Rozenberg

  5. Philipps-Universität Marburg, Germany

    Gabriele Taentzer

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Rosselló, F., Valiente, G. (2005). Graph Transformation in Molecular Biology. In: Kreowski, HJ., Montanari, U., Orejas, F., Rozenberg, G., Taentzer, G. (eds) Formal Methods in Software and Systems Modeling. Lecture Notes in Computer Science, vol 3393. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31847-7_7

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-31847-7_7

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-24936-8

  • Online ISBN: 978-3-540-31847-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation