Поваренная книга без списка продуктов — вот с чем сталкивается учёный, когда видит схему химических реакций. Стрелочки и формулы на бумаге выглядят стройно, но стоит начать искать в лаборатории молекулы, которые поведут себя именно так, — и начинается настоящий квест.
Авторы работы взяли за основу жёсткое правило: в каждой реакции число атомов слева и справа должно совпадать (это называют сохранением массы). Казалось бы, простая арифметика. Но когда нужно подобрать конкретные вещества из огромного каталога известных молекул, а заодно уложиться в разрешённые типы химических превращений, задача превращается в головоломку невероятной сложности.
И всё же выход нашёлся. Исследователи применили алгоритм с возвратами и отсечениями — он похож на игру в шахматы вслепую: перебираешь ходы, но безжалостно отбрасываешь те, что ведут в тупик. Такой подход, вдохновлённый поиском одинаковых фрагментов в графах (задача поиска подграфа), позволяет на практике собирать работающие молекулярные схемы для сложных систем — от экологии до медицины.
Книга рецептов обретает плоть. И за этим стоит не магия, а точный расчёт, который учит нас: даже в хаосе химических возможностей есть своя строгая логика.
как её написали авторы, на английском 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.
Многие биохимические сети в клетке до сих пор не удаётся воспроизвести «в пробирке» именно из-за того, что мы не можем подобрать правильные молекулы-участники — хотя все реакции на бумаге известны.