Un livre de recettes sans liste de courses, voilà ce que découvre un scientifique face à un schéma de réactions chimiques. Les flèches et les formules sur le papier semblent cohérentes, mais dès qu'on cherche en laboratoire des molécules qui se comporteront exactement comme prévu, la véritable chasse au trésor commence.
Les auteurs de l'étude se sont appuyés sur une règle stricte : dans chaque réaction, le nombre d'atomes à gauche et à droite doit être identique (ce qu'on appelle la conservation de la masse). Cela semble être une simple affaire d'arithmétique. Mais lorsqu'il faut choisir des substances concrètes parmi un vaste catalogue de molécules connues, tout en respectant les types de transformations chimiques autorisés, la tâche se transforme en casse-tête d'une complexité incroyable.
Et pourtant, une issue a été trouvée. Les chercheurs ont appliqué un algorithme avec retours arrière et élagage — un peu comme jouer aux échecs à l'aveugle : on explore les coups, mais on élimine sans pitié ceux qui mènent à une impasse. Cette approche, inspirée par la recherche de motifs identiques dans les graphes (le problème de la recherche de sous-graphes), permet en pratique d'assembler des schémas moléculaires fonctionnels pour des systèmes complexes — de l'écologie à la médecine.
Le livre de recettes prend chair. Et derrière cela, il n'y a pas de magie, mais un calcul précis qui nous apprend que même dans le chaos des possibilités chimiques, il existe une logique rigoureuse.
tel que rédigé par les auteurs, en anglais 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.
De nombreux réseaux biochimiques dans la cellule n'ont toujours pas pu être reproduits « en éprouvette », précisément parce que nous ne parvenons pas à choisir les bonnes molécules participantes — même si toutes les réactions sont connues sur le papier.