Inferring chemical reaction patterns using rule composition in graph grammars

Journal of Systems Chemistry - 2013
Jakob L Andersen1,2, Christoph Flamm3, Daniel Merkle2, Peter F Stadler4,5,6,7,8,3
1Max-Planck-Institute for Mathematics in the Sciences, Leipzig, Germany
2Department of Mathematics and Computer Science, University of Southern Denmark, Odense M, Denmark
3Institute for Theoretical Chemistry, University of Vienna, Wien, Austria
4Santa Fe Institute, Santa Fe, USA
5Center for non-coding RNA in Technology and Health, University of Copenhagen, Frederiksberg C, Denmark
6Bioinformatics Group, Department of Computer Science; and Interdisciplinary Center for Bioinformatics, University of Leipzig, Leipzig, Germany
7Fraunhofer Institute for Cell Therapy and Immunology, Leipzig, Germany
8Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany

Tóm tắt

Modeling molecules as undirected graphs and chemical reactions as graph rewriting operations is a natural and convenient approach to modeling chemistry. Graph grammar rules are most naturally employed to model elementary reactions like merging, splitting, and isomerisation of molecules. It is often convenient, in particular in the analysis of larger systems, to summarize several subsequent reactions into a single composite chemical reaction. We introduce a generic approach for composing graph grammar rules to define a chemically useful rule compositions. We iteratively apply these rule compositions to elementary transformations in order to automatically infer complex transformation patterns. As an application we automatically derive the overall reaction pattern of the Formose cycle, namely two carbonyl groups that can react with a bound glycolaldehyde to a second glycolaldehyde. Rule composition also can be used to study polymerization reactions as well as more complicated iterative reaction schemes. Terpenes and the polyketides, for instance, form two naturally occurring classes of compounds of utmost pharmaceutical interest that can be understood as “generalized polymers” consisting of five-carbon (isoprene) and two-carbon units, respectively. The framework of graph transformations provides a valuable set of tools to generate and investigate large networks of chemical networks. Within this formalism, rule composition is a canonical technique to obtain coarse-grained representations that reflect, in a natural way, “effective” reactions that are obtained by lumping together specific combinations of elementary reactions.

Từ khóa


Tài liệu tham khảo

Klamt S, Haus UU, Theis F: Hypergraphs and cellular networks. PLoS Comput Biol 2009,5(5):e1000385. 10.1371/journal.pcbi.1000385

Dittrich P, Ziegler J, Banzhaf W: Artificial chemistries – a review. Artif Life 2001,7(3):225–275. 10.1162/106454601753238636

Benkö G, Flamm C, Stadler PF: A graph-based toy model of chemistry. J Chem Inf Comput Sci 2003,43(4):1085–1093. 10.1021/ci0200570

Aittokallio T, Schwikowski B: Graph-based methods for analysing networks in cell biology. Brief Bioinform 2006,7(3):243–255. 10.1093/bib/bbl022

Orth JD, Thiele I, Palsson BØ: What is flux balance analysis? Nature Biotech 2010, 28: 245–248. 10.1038/nbt.1614

Schuster S, Fell DA, Dandekar T: A general definition of metabolic pathways useful for systematic organization and analysis of complex metabolic networks. Nature Biotech 2000, 18: 326–332. 10.1038/73786

Price ND, Reed JL, Papin JA, Wiback SJ, Palsson BØ: Network-based analysis of metabolic regulation in the human red blood cell. J Theor Biol 2003, 225: 185–194. 10.1016/S0022-5193(03)00237-6

Larhlimi A, Bockmayr A: A new constraint-based description of the steady-state flux cone of metabolic networks. Discr Appl Math 2009, 157: 2257–2266. 10.1016/j.dam.2008.06.039

Félix L, Rosselló F, Valiente G: Efficient reconstruction of metabolic pathways by bidirectional chemical search. Bull Math Biol 2009, 71: 750–769. 10.1007/s11538-008-9380-8

Ehrig H, Ehrig K, Prange U, Taenthzer G: Fundamentals of Algebraic Graph Transformation. Berlin: Springer-Verlag; 2006.

Rosselló F, Valiente G: Graph transformation in molecular biology. Lect Notes Comp Sci 2005, 3393: 116–133. 10.1007/978-3-540-31847-7_7

Danos V, Feret J, Fontana W, Harmer R, Hayman J, Krivine J, Thompson-Walsh C, Winskel G: Graphs, rewriting and pathway reconstruction for rule-based models. Leibniz Int Proc Inf 2012. in press

Golas U: Analysis and Correctness of Algebraic Graph and Model Transformations. Wiesbaden: Vieweg+Teubner; 2010.

Ehrig H, Habel A, Kreowski HJ, Parisi-Presicce F: Parallelism and concurrency in high-level replacement systems. Math Struct Comp Sci 1991, 1: 361–404. 10.1017/S0960129500001353

Flamm C, Ullrich A, Ekker H, Mann M, Hogerl D, Rohrschneider M, Sauer S, Scheuermann G, Klemm K, Hofacker I, Stadler PF: Evolution of metabolic networks: a computational frame-work. J Syst Chem 2010,1(1):4. 10.1186/1759-2208-1-4

Mann M, Ekker H, Flamm C: The graph grammar library – a generic framework for chemical graph rewrite systems. 2013.http://arxiv.org/abs/1304.1356 []

Hompage of the Graph Grammar Library (GGL) [The source code and the documentation of the library can be accessed via, http://www.tbi.univie.ac.at/software/GGL/] [The source code and the documentation of the library can be accessed via, ]

Kanehisa M, Goto S, Sato Y, Furumichi M, Tanabe M: KEGG for integration and interpretation of large-scale molecular data sets. Nucleic Acids Res 2012, 40: D109–114. 10.1093/nar/gkr988

Caspi R, Altman T, Dreher K, Fulcher CA, Subhraveti P, Keseler IM, Kothari A, Krummenacker M, Latendresse M, Mueller LA, Ong Q, Paley S, Pujar A, Shearer AG, Travers M, Weerasinghe D, Zhang P, Karp PD: The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of pathway/genome databases. Nucleic Acids Res 2012, 40: D742–753. 10.1093/nar/gkr1014

Holliday GL, Andreini C, Fischer JD, Rahman SA, Almonacid DE, Williams ST, Pearson WR: MACiE: exploring the diversity of biochemical reactions. Nucleic Acids Res 2012, 40: D783–789. 10.1093/nar/gkr799

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 Handbook of Graph Grammars and Computing by Graph Transformations. Edited by: Rozenberg G. Singapore: World Scientific; 1997:247–312.

Löwe M: Algebraic approach to single-pushout graph transformation. Theor Comp Sci 1993, 109: 181–224. 10.1016/0304-3975(93)90068-5

Ehrig H: Introduction to the algebraic theory of graph grammars. Lect Notes Comp Sci 1979, 13: 1–69.

Thông tin
Thông tin xuất bản

Journal of Systems Chemistry

Thông tin tác giả