Peter F. Stadler

SFI Seminar:

Monday, March 25, 2013 • 12:15 p.m. • Collins Conference Room

Graph Grammars and Directed Hypergraphs: Discrete Models of Chemistry

Peter F. Stadler, University of Leipzig; SFI External Professor

Abstract: Labeled (multi)graphs have a long tradition as models of molecules as witnessed by the field of “chemical graph theory.”

Chemical reactions, in this setting, are naturally thought of as graph transformations, a notion that goes back to the work Dugundji and Ugi.

In a more convenient framework chemical reaction mechanism are seen as transformation rules, i.e., productions in a graph grammar, thus interpreting chemical reactions formally as derivations.

Graph grammars come in different flavors, depending of the way they are rooted in category theory.

Albeit equivalent to single pushout approaches for chemically relevant transformations, the double-pushout (DPO) formalism offers the advantage of providing explicit access to a model of the transition state and hence a direct link to the “imaginary transition states” encoding the reaction mechanisms.

An interesting facet of this approach is usefulness of rule compositions, borrowed from concurrency theory, as a practical means to analyze complex transformation patterns.

As a generative model, graph grammars can produce large-scale model of chemical reaction networks from a small set of “seed molecules.”

In this setting, each reaction (derivation) corresponds to a directed hyperedge. In contrast to the plethora of efficient algorithmic approaches to analyze undirected or even directed graphs, very little is known for directed hypergraphs, and even computational problems that are well tractable in graphs are NP hard in hypergraphs.

This is in particular true for flux maximization problems and the recognition of autocatalysis. On the other hand, many of these tasks are tractable in practice even for large networks because the problems lend themselves in a natural way to Integer Linear Programming formulations. This is framework is implemented as a software tool.

Ongoing work explores in particular two avenues: On the one hand, the spatial structure of molecules implies the existence of a complex stereochemistry that cannot always be neglected.

An added level of realism can be incorporated into the discrete models by adding local orderings on the adjacencies. On the other hand, the relationships between a reaction network’s hypergraph representation and the condensed graph “caricatures” known as substance graph and reaction graph is explored systematically.

More practical applications concern, for example, the investigation of the HCN polymers that play an important role in models of early chemical evolution as well as in present-day astrochemistry.

Note: We are unable to accommodate members of the public for SFI’s limited lunch service; you’re welcome to bring your own.

SFI Host: Jennifer Dunne

Click here to view the online event listing.

The Santa Fe Institute is a nonprofit research center located in Santa Fe, New Mexico. Its scientists collaborate across disciplines to understand the complex systems that underlie critical questions for science and humanity. The Institute is supported by philanthropic individuals and foundations, forward-thinking partner companies, and government science agencies.