Santa Fe Institute

Seminar

March 25, 2013
12:15 PM
Collins Conference Room

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.

Purpose: Research Collaboration

SFI Host: Jennifer Dunne

More Info

• * SFI community lectures are free, open, & accessible to the public.
• * Seminars & colloquia are geared for scientists but free & open to the interested public.
• * All other SFI events are by invitation only.
• * Note: We are unable to accommodate members of the public for SFI's limited lunch service; you're welcome to bring your own.