Crossover operators for molecular graphs with an application to virtual drug screening
Open Access
- 17 June 2025
- journal article
- research article
- Published by Springer Nature in Journal of Cheminformatics
- Vol. 17 (1) , 1-26
Abstract
Genetic algorithms are a powerful method to solve optimization problems with complex cost functions over vast search spaces that rely in particular on recombining parts of previous solutions. Crossover operators play a crucial role in this context. Here, we describe a large class of these operators designed for searching over spaces of graphs. These operators are based on introducing small cuts into graphs and rejoining the resulting induced subgraphs of two parents. This form of cut-and-join crossover can be restricted in a consistent way to preserve local properties such as vertex-degrees (valency), or bond-orders, as well as global properties such as graph-theoretic planarity. In contrast to crossover on strings, cut-and-join crossover on graphs is powerful enough to ergodically explore chemical space even in the absence of mutation operators. Extensive benchmarking shows that the offspring of molecular graphs are again plausible molecules with high probability, while at the same time crossover drastically increases the diversity compared to initial molecule libraries. Moreover, desirable properties such as favorable indices of synthesizability are preserved with sufficient frequency that candidate offsprings can be filtered efficiently for such properties. As an application we utilized the cut-and-join crossover in , a GA-based system for computer-aided drug design. In optimization runs searching for ligands binding to four different target proteins we consistently found candidate molecules with binding constants exceeding the best known binders as well as candidates found in make-on-demand libraries. Scientific contribution We define cut-and-join crossover operators on a variety of graph classes including molecular graphs. This constitutes a mathematically simple and well-characterized approach to recombination of molecules that performed very well in real-life CADD tasks.Keywords
All Related Versions
Funding Information
- Deutsche Forschungsgemeinschaft (460865652, 209933838)
- Novo Nordisk Foundation (0066551)
- Center of Excellence for AI-research Center for Scalable Data Analytics and Artificial Intelligence Dresden/Leipzig (SCADS24B)
- Max Kade Foundation (Fellowship)
- Bundesministerium für Forschung, Technologie und Raumfahrt (57616814)
- NIH (R01 DA046138)
- Alexander von Humboldt Foundation (Humboldt Professorship)
- de.NBI
- Universität Leipzig
This publication has 80 references indexed in Scilit:
- List Covering of Regular Multigraphs with Semi-edgesAlgorithmica, 2023
- So you think you understand tautomerism?Journal of Computer-Aided Molecular Design, 2010
- Let’s not forget tautomersJournal of Computer-Aided Molecular Design, 2009
- Molecules with Nonstandard Topological Properties: Centrohexaindane, Kuratowski's Cyclophane and Other Graph‐theoretically Nonplanar Molecules2009
- Efficient Algorithms for the Problems of Enumerating Cuts by Non-decreasing WeightsAlgorithmica, 2009
- About the Complexity of Timetables and 3-Dimensional Discrete Tomography: A Short Proof of NP-Hardness2009
- On the Art of Compiling and Using 'Drug‐Like' Chemical Fragment SpacesChemMedChem, 2008
- Reconstructing a Matrix with a Given List of Coefficients and Prescribed Row and Column Sums Is NP-Hard2008
- Optimization of the Biological Activity of Combinatorial Compound Libraries by a Genetic AlgorithmAngewandte Chemie International Edition, 1995
- On the structure of all minimum cuts in a network and applications1980