Crossover Operators for Molecular Graphs with an Application to Virtual Drug Screening
Preprint
- 17 September 2024
- preprint
- Published by American Chemical Society (ACS) in ChemRxiv
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 REvoLd, 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. Taken together, cut-and-join crossover operators constitute a mathematically simple and well-characterized approach to recombination of molecules that performed very well in real-life CADD tasks.Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- Galileo: Three-dimensional searching in large combinatorial fragment spaces on the example of pharmacophoresJournal of Computer-Aided Molecular Design, 2022
- Generating Multibillion Chemical Space of Readily Accessible Screening CompoundsiScience, 2020
- Evolutionary algorithms for de novo drug design – A surveyApplied Soft Computing, 2015
- So you think you understand tautomerism?Journal of Computer-Aided Molecular Design, 2010
- Efficient Algorithms for the Problems of Enumerating Cuts by Non-decreasing WeightsAlgorithmica, 2009
- On the Art of Compiling and Using 'Drug‐Like' Chemical Fragment SpacesChemMedChem, 2008
- Virtual screening strategies in drug discoveryCurrent Opinion in Chemical Biology, 2007
- ChemInform Abstract: Optimization of the Biological Activity of Combinatorial Compound Libraries by a Genetic Algorithm.ChemInform, 1996
- Automatic generation of 3D-atomic coordinates for organic moleculesTetrahedron Computer Methodology, 1990
- On the structure of all minimum cuts in a network and applications1980