Source author record

Christoph Flamm

Christoph Flamm appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Molecular Networks Biomolecules Discrete Mathematics Formal Languages and Automata Theory Computational Engineering, Finance, and Science physics.chem-ph Computational Complexity Data Structures and Algorithms math.CO math.MG Mathematical Software

Catalog footprint

What is connected

11works

11topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Representing catalytic mechanisms with rule composition

Reaction mechanisms are often presented as sequences of elementary steps, such as codified by arrow pushing. We propose an approach for representing such mechanisms using graph transformation. In this framework, each elementary step is a rule for modifying a molecular graph and a mechanism is a sequence of such rules. To generate a compact representation of a multi-step reaction, we compose the rules of individual steps into a composite rule, providing a rigorous and fully automated approach to coarse-graining. While the composite rule retains the graphical conditions necessary for the execution of a mechanism, it also records information about transient changes not visible by comparing educts and products. By projecting the rule onto a single "overlay graph", we generalize Fujita's idea of an Imaginary Transition Structure from elementary reactions to composite reactions. The utility of the overlay graph construct is exemplified in the context of enzyme-catalyzed reactions. In a first application, we exploit mechanistic information in the Mechanism and Catalytic Site Atlas to construct overlay graphs of hydrolase reactions listed in the database. These graphs point at a spectrum of catalytic entanglement of enzyme and substrate, de-emphasizing the notion of a singular catalyst in favor of a collection of catalytic sites that can be distributed across enzyme and substrate. In a second application, we deploy composite rules to search the Rhea database for reactions of known or unknown mechanism that are, in principle, compatible with the mechanisms implied by the composite rules. We believe this work adds to the utility of graph-transformation formalisms in representing and reasoning about chemistry in an automated yet insightful fashion.

preprint2022arXiv

What makes a reaction network "chemical"?

Reaction networks (RNs) comprise a set $X$ of species and a set $\mathscr{R}$ of reactions $Y\to Y'$, each converting a multiset of educts $Y\subseteq X$ into a multiset $Y'\subseteq X$ of products. RNs are equivalent to directed hypergraphs. However, not all RNs necessarily admit a chemical interpretation. Instead, they might contradict fundamental principles of physics such as the conservation of energy and mass or the reversibility of chemical reactions. The consequences of these necessary conditions for the stoichiometric matrix $\mathbf{S} \in \mathbb{R}^{X\times\mathscr{R}}$ have been discussed extensively in the literature. Here, we provide sufficient conditions for $\mathbf{S}$ that guarantee the interpretation of RNs in terms of balanced sum formulas and structural formulas, respectively. Chemically plausible RNs allow neither a perpetuum mobile, i.e., a "futile cycle" of reactions with non-vanishing energy production, nor the creation or annihilation of mass. Such RNs are said to be thermodynamically sound and conservative. For finite RNs, both conditions can be expressed equivalently as properties of $\mathbf{S}$. The first condition is vacuous for reversible networks, but it excludes irreversible futile cycles and - in a stricter sense - futile cycles that even contain an irreversible reaction. The second condition is equivalent to the existence of a strictly positive reaction invariant. Furthermore, it is sufficient for the existence of a realization in terms of sum formulas, obeying conservation of "atoms". In particular, these realizations can be chosen such that any two species have distinct sum formulas, unless $\mathbf{S}$ implies that they are "obligatory isomers". In terms of structural formulas, every compound is a labeled multigraph, in essence a Lewis formula, and reactions comprise only a rearrangement of bonds such that the total bond order is preserved.

preprint2016arXiv

A Software Package for Chemically Inspired Graph Transformation

Chemical reaction networks can be automatically generated from graph grammar descriptions, where rewrite rules model reaction patterns. Because a molecule graph is connected and reactions in general involve multiple molecules, the rewriting must be performed on multisets of graphs. We present a general software package for this type of graph rewriting system, which can be used for modelling chemical systems. The package contains a C++ library with algorithms for working with transformation rules in the Double Pushout formalism, e.g., composition of rules and a domain specific language for programming graph language generation. A Python interface makes these features easily accessible. The package also has extensive procedures for automatically visualising not only graphs and rewrite rules, but also Double Pushout diagrams and graph languages in form of directed hypergraphs. The software is available as an open source package, and interactive examples can be found on the accompanying webpage.

preprint2016arXiv

Automatic Inference of Graph Transformation Rules Using the Cyclic Nature of Chemical Reactions

Graph transformation systems have the potential to be realistic models of chemistry, provided a comprehensive collection of reaction rules can be extracted from the body of chemical knowledge. A first key step for rule learning is the computation of atom-atom mappings, i.e., the atom-wise correspondence between products and educts of all published chemical reactions. This can be phrased as a maximum common edge subgraph problem with the constraint that transition states must have cyclic structure. We describe a search tree method well suited for small edit distance and an integer linear program best suited for general instances and demonstrate that it is feasible to compute atom-atom maps at large scales using a manually curated database of biochemical reactions as an example. In this context we address the network completion problem.

preprint2015arXiv

Support for Eschenmoser's Glyoxylate Scenario

A core topic of research in prebiotic chemistry is the search for plausible synthetic routes that connect the building blocks of modern life such as sugars, nucleotides, amino acids, and lipids to "molecular food sources" that have likely been abundant on Early Earth. In a recent contribution, Albert Eschenmoser emphasised the importance of catalytic and autocatalytic cycles in establishing such abiotic synthesis pathways. The accumulation of intermediate products furthermore provides additional catalysts that allow pathways to change over time. We show here that generative models of chemical spaces based on graph grammars make it possible to study such phenomena is a systematic manner. In addition to repro- ducing the key steps of Eschenmoser's hypothesis paper, we discovered previously unexplored potentially autocatalytic pathways from HCN to glyoxylate. A cascading of autocatalytic cycles could efficiently re-route matter, distributed over the combinatorial complex network of HCN hydrolysation chemistry, towards a potential primordial metabolism. The generative approach also has it intrinsic limitations: the unsupervised expansion of the chemical space remains infeasible due to the exponential growth of possible molecules and reactions between them. Here in particular the combinatorial complexity of the HCN polymerisation and hydrolysation networks forms the computational bottleneck. As a consequence, guidance of the computational exploration by chemical experience is indispensable.

preprint2014arXiv

Generic Strategies for Chemical Space Exploration

Computational approaches to exploring "chemical universes", i.e., very large sets, potentially infinite sets of compounds that can be constructed by a prescribed collection of reaction mechanisms, in practice suffer from a combinatorial explosion. It quickly becomes impossible to test, for all pairs of compounds in a rapidly growing network, whether they can react with each other. More sophisticated and efficient strategies are therefore required to construct very large chemical reaction networks. Undirected labeled graphs and graph rewriting are natural models of chemical compounds and chemical reactions. Borrowing the idea of partial evaluation from functional programming, we introduce partial applications of rewrite rules. Binding substrate to rules increases the number of rules but drastically prunes the substrate sets to which it might match, resulting in dramatically reduced resource requirements. At the same time, exploration strategies can be guided, e.g. based on restrictions on the product molecules to avoid the explicit enumeration of very unlikely compounds. To this end we introduce here a generic framework for the specification of exploration strategies in graph-rewriting systems. Using key examples of complex chemical networks from sugar chemistry and the realm of metabolic networks we demonstrate the feasibility of a high-level strategy framework. The ideas presented here can not only be used for a strategy-based chemical space exploration that has close correspondence of experimental results, but are much more general. In particular, the framework can be used to emulate higher-level transformation models such as illustrated in a small puzzle game.

preprint2014arXiv

Memory efficient RNA energy landscape exploration

Energy landscapes provide a valuable means for studying the folding dynamics of short RNA molecules in detail by modeling all possible structures and their transitions. Higher abstraction levels based on a macro-state decomposition of the landscape enable the study of larger systems, however they are still restricted by huge memory requirements of exact approaches. We present a highly parallelizable local enumeration scheme that enables the computation of exact macro-state transition models with highly reduced memory requirements. The approach is evaluated on RNA secondary structure landscapes using a gradient basin definition for macro-states. Furthermore, we demonstrate the need for exact transition models by comparing two barrier-based appoaches and perform a detailed investigation of gradient basins in RNA energy landscapes. Source code is part of the C++ Energy Landscape Library available at http://www.bioinf.uni-freiburg.de/Software/.

preprint2013arXiv

On the Complexity of Reconstructing Chemical Reaction Networks

The analysis of the structure of chemical reaction networks is crucial for a better understanding of chemical processes. Such networks are well described as hypergraphs. However, due to the available methods, analyses regarding network properties are typically made on standard graphs derived from the full hypergraph description, e.g.\ on the so-called species and reaction graphs. However, a reconstruction of the underlying hypergraph from these graphs is not necessarily unique. In this paper, we address the problem of reconstructing a hypergraph from its species and reaction graph and show NP-completeness of the problem in its Boolean formulation. Furthermore we study the problem empirically on random and real world instances in order to investigate its computational limits in practice.

preprint2013arXiv

The Graph Grammar Library - a generic framework for chemical graph rewrite systems

Graph rewrite systems are powerful tools to model and study complex problems in various fields of research. Their successful application to chemical reaction modelling on a molecular level was shown but no appropriate and simple system is available at the moment. The presented Graph Grammar Library (GGL) implements a generic Double Push Out approach for general graph rewrite systems. The framework focuses on a high level of modularity as well as high performance, using state-of-the-art algorithms and data structures, and comes with extensive documentation. The large GGL chemistry module enables extensive and detailed studies of chemical systems. It well meets the requirements and abilities envisioned by Yadav et al. (2004) for such chemical rewrite systems. Here, molecules are represented as undirected labeled graphs while chemical reactions are described by according graph grammar rules. Beside the graph transformation, the GGL offers advanced cheminformatics algorithms for instance to estimate energies ofmolecules or aromaticity perception. These features are illustrated using a set of reactions from polyketide chemistry a huge class of natural compounds of medical relevance. The graph grammar based simulation of chemical reactions offered by the GGL is a powerful tool for extensive cheminformatics studies on a molecular level. The GGL already provides rewrite rules for all enzymes listed in the KEGG LIGAND database is freely available at http://www.tbi.univie.ac.at/software/GGL/.

preprint2012arXiv

Inferring Chemical Reaction Patterns Using Rule Composition in Graph Grammars

Modeling molecules as undirected graphs and chemical reactions as graph rewriting operations is a natural and convenient approach tom odeling 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 use 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. This is useful for instance to understand the net effect of complex catalytic cycles such as the Formose reaction. The automatically inferred graph grammar rule is a generic representative that also covers 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.

preprint2011arXiv

Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete

Background: A classical problem in metabolic design is to maximize the production of desired compound in a given chemical reaction network by appropriately directing the mass flow through the network. Computationally, this problem is addressed as a linear optimization problem over the "flux cone". The prior construction of the flux cone is computationally expensive and no polynomial-time algorithms are known. Results: Here we show that the output maximization problem in chemical reaction networks is NP-complete. This statement remains true even if all reactions are monomolecular or bimolecular and if only a single molecular species is used as influx. As a corollary we show, furthermore, that the detection of autocatalytic species, i.e., types that can only be produced from the influx material when they are present in the initial reaction mixture, is an NP-complete computational problem. Conclusions: Hardness results on combinatorial problems and optimization problems are important to guide the development of computational tools for the analysis of metabolic networks in particular and chemical reaction networks in general. Our results indicate that efficient heuristics and approximate algorithms need to be employed for the analysis of large chemical networks since even conceptually simple flow problems are provably intractable.