Crossover operators for molecular graphs with an application to virtual drug screening

Area of Science:

• Computational chemistry
• Bioinformatics
• Machine learning

Background:

• Genetic algorithms (GAs) are effective for complex optimization problems.
• Crossover operators are key for recombining solutions in GAs.
• Graph-based representations are crucial for molecular structures.

Purpose of the Study:

• To introduce a novel class of cut-and-join crossover operators for graph-based genetic algorithms.
• To ensure these operators preserve essential molecular properties.
• To apply these operators in computer-aided drug design.

Main Methods:

• Defined cut-and-join crossover operators for various graph classes, including molecular graphs.
• Restricted operators to preserve local (e.g., vertex-degrees) and global (e.g., planarity) properties.
• Benchmarked operator performance on molecular graph generation and diversity.

Main Results:

• Cut-and-join crossover efficiently explores chemical space, even without mutation.
• Offspring molecular graphs are highly probable and increase library diversity.
• Desirable properties like synthesizability are preserved, enabling efficient filtering.
• Applied in a GA-based drug design system (REvoLd) to find potent ligands.

Conclusions:

• Cut-and-join crossover provides a mathematically sound and effective method for molecular recombination.
• This approach significantly enhances computer-aided drug design tasks.
• The operators are versatile and applicable to various graph classes.