Atom-to-atom maps (AAMs) are bijections that establish the correspondence of reactant and product atoms across chemical reactions. They capture crucial features of the reaction mechanism and thus play a central role in modeling chemistry at the level of graph transformations. AAMs are equivalent to so-called “imaginary transition state” (ITS) graphs, making it possible to reduce tasks such as the computational comparison of AAMs to testing graph isomorphisms. In many application scenarios, nonetheless, only partial information is available, i.e., only partial maps or, equivalently, only subgraphs of the ITS graphs, are known. Here, we investigate whether and how, and to what extent, such partial chemical data can be completed and compared. The focus of this contribution is entirely on the development of a solid mathematical foundation for the analysis of partial AAMs and their associated partial ITS graphs.
1 February 2023 in Match Communications in Mathematical and in Computer Chemistry
The comparison of multiple (labeled) graphs with unrelated vertex sets is an important task in diverse areas of applications. Conceptually, it is often closely related to multiple sequence alignments since one aims to determine a correspondence, or more precisely, a multipartite matching between the vertex sets. There, the goal is to match vertices that are similar in terms of labels and local neighborhoods. Alignments of sequences and ordered forests, however, have a second aspect that does not seem to be considered for graph comparison, namely the idea that an alignment is a superobject from which the constituent input objects can be recovered faithfully as well-defined projections. Progressive alignment algorithms are based on the idea of computing multiple alignments as a pairwise alignment of the alignments of two disjoint subsets of the input objects. Our formal framework guarantees that alignments have compositional properties that make alignments of alignments well-defined. The various similarity-based graph matching constructions do not share this property and solve substantially different optimization problems. We demonstrate that optimal multiple graph alignments can be approximated well by means of progressive alignment schemes. The solution of the pairwise alignment problem is reduced formally to computing maximal common induced subgraphs. Similar to the ambiguities arising from consecutive indels, pairwise alignments of graph alignments require the consideration of ambiguous edges that may appear between alignment columns with complementary gap patterns. We report a simple reference implementation in Python/NetworkX intended to serve as starting point for further developments. The computational feasibility of our approach is demonstrated on test sets of small graphs that mimimc in particular applications to molecular graphs.
10 March 2025 in The Art of Discrete and Applied Mathematics
The Art of Discrete and Applied Mathematics (ADAM) is a modern, dynamic, platinum open access, electronic journal that will publish high-quality articles of arbitrary length in contemporary discrete and applied mathematics in which neither the authors nor the readers incur any costs.
Chemical reaction databases typically report the molecular structures of reactant and product compounds, as well as their stoichiometry, but lack information, in particular, on the correspondence of reactant and product atoms. These atom-to-atom maps (AAM), however, are crucial for applications including chemical synthesis planning in organic chemistry and the analysis of isotope labeling experiments in modern metabolomics. AAMs therefore need to be reconstructed computationally. This situation is aggravated, furthermore, by the fact that chemically correct AAMs are, fundamentally, determined by quantum-mechanical phenomena and thus cannot be reliably computed by solving graph-theoretical optimization problems defined by the reactant and product structures. A viable solution for this problem is to shift the focus into first identifying a partial AAM containing the reaction center, i.e., covering the atoms incident with all bonds that change during a reaction. This then leads to the problem of extending the partial map to the full reaction. The AAM of a reaction is faithfully represented by the Imaginary Transition State (ITS) graph, providing a convenient graph-theoretic framework to address the questions of when and how a partial AAM can be extended. We show that an unique extension exists whenever, and only if, these partial AAMs cover the reaction center. Moreover, uniqueness results are generalized to partial AAMs in situations where hydrogen atoms are not represented explicitly. In this case their extension can be computed by solving a constrained graph-isomorphism search between specific subgraphs of ITS graphs. We close by benchmarking different tools for this task.
SynTemp is a framework designed to extract and hierarchically cluster reaction templates from large-scale reaction data repositories. Reaction templates are partial Imaginary Transition State graphs representing the reaction center as well as surrounding context. These graphs are equivalent to Double Pushout graph rewriting rules and thus can be applied directly to predict reaction outcomes at structural formula level. Rule inference is based on a consensus of multiple atom-atom mapping (AAM) tools integrating predictions RXNMapper, GraphormerMapper, and LocalMapper based on a robust graph-theoretic methodology for comparing partial atom-atom mappings. SynTemp achieves an exceptional accuracy of 99.5% and a success rate of 71.23% in obtaining AAMs on the Chemical Reaction Dataset. Reaction centers with surrounding contexts are extracted and completed with mechanistically relevant hydrogen atoms to obtain complete reaction templates. Subsequently, they were categorized into distinct groups based on topological features using hierarchical clustering, resulting in a library of 311 transformation rules that explains 86% of the reaction data set. A residual of 14% remained unresolved due to non-equivalent AAMs and ambiguous hydrogen placements. Despite these challenges, the coverage of our templates remains high at approximately 93.5-94.5%, surpassing that of RDChiral using SMARTS templates.