2022/01/12 by Jakob L. Andersen, Rolf Fagerberg, Andersen, Jakob L. +9
Biochemistry, Genetics and Molecular Biology · Computer Science · Materials Science · #Computational Drug Discovery Methods #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Machine Learning in Materials Science #Microbial Metabolic Engineering and Bioproduction
paper · pdf · doi:10.48550/arxiv.2201.04360
openalex publication_date 2022/01/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph transformation formalisms have proven to be suitable tools for the modelling of chemical reactions. They are well established in theoretical studies and increasingly also in practical applications in chemistry. The latter is made feasible via the development of programming frameworks which makes the formalisms executable. The application of such frameworks to large networks of chemical reactions, however, poses unique computational challenges. One such characteristic is the inherent combinatorial nature of the graphs involved. The graphs consist of many connected components, representing individual molecules. While the existing methods for implementing graph transformations can be applied to such graphs, the combinatorics of constructing graph matches quickly becomes a computational bottleneck as the size of the chemical reaction network grows. In this contribution, we develop a new method of enumerating graph matches during graph transformation rule application. The method is designed to improve performance in such scenarios and is based on constructing graph matches in an iterative, component-wise fashion which allows redundant applications to be detected early and pruned. We further extend the algorithm with an efficient heuristic based on local symmetries of the graphs, which allow us to detect and discard isomorphic applications early. Finally, we conduct chemical network generation experiments on real-life as well as synthetic data and compare against the state-of-the-art algorithm in the field.