Enumeration Approach to Atom-to-Atom Mapping Accelerated by Ising Computing

Chemical reactions are regarded as transformations of
chemical
structures, and the question of which atoms in the reactants correspond
to which atoms in the products has attracted chemists for a long time.
Atom-to-atom mapping (AAM) is a procedure that establishes such correspondence(s)
between the atoms of reactants and products in a chemical reaction.
Currently, automatic AAM tools play a pivotal role in various chemoinformatics
tasks. However, achieving accurate automatic AAM for complex or unknown
reactions within a reasonable computation time remains a significant
challenge due to the combinatorial nature of the problem and the difficulty
in applying appropriate reaction rules. In this study, we propose
a rule-free AAM algorithm, which enumerates all atom-to-atom correspondences
that minimize the number of bond cleavages and formations during the
reaction. To reduce the computational burden associated with the combinatorial
optimization (i.e., minimizing bond changes), we introduce Ising computing,
a computing paradigm that has gained significant attention for its
efficiency in solving hard combinatorial optimization problems. We
found that our Ising computing framework outperforms conventional
combinatorial optimization algorithms in terms of computation times,
making it feasible to solve the AAM problem without reaction rules
in an acceptable time. Furthermore, our AAM algorithm successfully
found the correct AAM solution for all problems in a benchmark data
set. In contrast, conventional AAM algorithms based on chemical heuristics
failed for several problems. Specifically, these algorithms either
failed to find the optimal solution in terms of bond changes, or they
identified only one optimal solution, which was incorrect when multiple
optimal solutions exist. These results emphasize the importance of
enumerating all optimal correspondences that minimize bond changes,
which is effectively achieved by our Ising-computing framework.