GENETIC ALGORITHM FOR ERROR-TOLERANT MATCHING OF MOLECULAR GRAPHS

The paper considers the problem of approximate structural matching of molecular graphs (Error-Tolerant Graph Matching). This is a relevant issue in chemoinformatics since classical exact algorithms are sensitive to structural errors and exhibit exponential complexity. The scientific novelty of this work lies in the development of specialized limited-search genetic operators (Bucket PMX, Bucket Smart Mutation), which, unlike existing analogs, integrate semantic constraints directly into the solution structure (valid-by-construction). This approach avoids the use of penalty functions and reduces the search space without losing valid solutions. The proposed method utilizes incremental cost assessment (Delta Evaluation) and WL-invariants to accelerate convergence. It was experimentally established that on the OGB-HIV dataset, the algorithm demonstrates stable performance with polynomial empirical complexity, and the fitness function correlates with the degree of structural differences, allowing its use as a similarity measure.