A cookbook without a shopping list: that's what a scientist faces when looking at a scheme of chemical reactions. The arrows and formulas on paper look neat, but once you start hunting in the lab for molecules that will actually behave that way, a real quest begins.
The authors based their work on a strict rule: in every reaction, the number of atoms on the left must equal the number on the right (this is called conservation of mass). Seems like simple arithmetic. But when you need to pick specific substances from a huge catalog of known molecules, while also staying within allowed types of chemical transformations, the task turns into a decision-making puzzle of incredible complexity.
Yet a way out was found. The researchers used a backtracking algorithm with pruning: it's like playing chess blindfolded: you try moves, but ruthlessly discard those that lead to dead ends. This approach, inspired by searching for identical fragments in graphs (the subgraph isomorphism problem), makes it possible in practice to assemble working molecular property prediction schemes for stochastic modeling of complex systems — from ecology to medicine.
The recipe book takes on flesh. And behind this is not magic, but precise calculation that teaches us: even in the chaos of chemical possibilities, there is a strict logic.
as written by the authors arXiv:2608.04635v1
Abstract reaction networks appear not only as models of chemical reactions but also as models of complex systems, with applications in areas such as ecology and epidemiology, and as one of several alternative paradigms for non-standard computation. It is therefore of interest to determine whether an abstract reaction network can be realized by a concrete set of molecules and plausible chemical reaction mechanisms. It is known that a reaction network has a realization in terms of chemical graphs (i.e., Lewis structures) if and only if it is conservative. Here we consider the problem of assigning a set M of known molecules to a set X of abstract entities in a reaction network (X,R) such that each reaction satisfies mass balance and adheres to one of an allowed set of chemical reaction mechanisms. We show that this problem is NP-complete. Nevertheless, it can be solved in practice using a backtrack-and-prune algorithm inspired by the VF2 family of algorithms originally designed for the subgraph isomorphism problem.
Many biochemical networks in the cell still cannot be reproduced 'in a test tube' precisely because we cannot pick the right participant molecules — even though all the reactions are known on paper.