A Genetic Algorithm for Navigating Synthesizable Molecular Spaces

The paper introduces SynGA, a lightweight genetic algorithm that operates directly on synthesis routes with custom operators to ensure molecular synthesizability, demonstrating state-of-the-art performance in property optimization tasks when combined with machine learning-based building block filtering.

The Gist

Imagine you are a master chef trying to invent a new, delicious dish. You have a massive pantry (the molecular space) filled with millions of ingredients (building blocks) and a cookbook full of cooking rules (reaction templates). Your goal is to create a dish that tastes amazing (has great properties) or looks exactly like a famous dish you love (analog search).

The problem? Most computer programs trying to help you are like wild dreamers. They might suggest a dish made of "glitter and rubber," which sounds cool but is impossible to actually cook in a real kitchen. If you spend weeks trying to make it, you'll fail.

This paper introduces SynGA (Synthesis Genetic Algorithm), a new tool that acts like a pragmatic, super-organized sous-chef who only suggests recipes you can actually cook.

Here is how it works, broken down into simple concepts:

1. The "Family Tree" of Recipes

Instead of just guessing random ingredients, SynGA thinks in terms of recipes (synthesis routes).

• The Metaphor: Imagine every possible dish has a family tree. The leaves of the tree are the raw ingredients you buy at the store. The branches are the cooking steps (mixing, heating, frying). The top of the tree is the final dish.
• The Innovation: Most AI tries to guess the final dish first and then tries to figure out how to make it later (often failing). SynGA builds the tree from the bottom up. It only creates dishes that have a valid, step-by-step recipe using ingredients that actually exist. It's impossible for SynGA to suggest a "glitter cake" because there is no recipe for it in its cookbook.

2. The Genetic Algorithm: "Survival of the Fittest Recipes"

SynGA uses a method called a Genetic Algorithm, which mimics evolution.

• The Population: It starts with a crowd of 500 different recipes (a population).
• The "Crossover" (Mixing): It takes two good recipes and swaps parts of them. Imagine taking the sauce from a pasta dish and the crust from a pizza to see if you can make a "pizza-pasta" that tastes great.
• The "Mutation" (Tweaking): It randomly changes a step. Maybe it swaps "salt" for "pepper" or changes the cooking time.
• The Selection: It tastes all the new dishes. The ones that taste the best (have the best properties) survive to make the next generation. The bad ones are thrown out.

3. The "Smart Filter" (The ML Magic)

The pantry has 200,000 ingredients. Checking every single one for every recipe would take forever.

• The Metaphor: Imagine you have a smart librarian (Machine Learning) who knows exactly which ingredients are likely to work for the specific dish you want.
• How it helps: Before the "sous-chef" (SynGA) starts cooking, the librarian says, "For this specific soup, ignore the 190,000 ingredients you don't need. Just look at these top 100."
• The Result: This makes the search incredibly fast and efficient. It's like searching for a needle in a haystack, but the librarian has already removed 99% of the hay.

4. Two Main Jobs

The paper shows SynGA doing two specific tasks:

• Job A: The "Look-Alike" Search (Analog Search)

  • Scenario: You have a drug that works, but it's too expensive to make. You want a "cousin" molecule that works just as well but uses cheaper ingredients.
  • SynGA's Role: It finds a molecule that looks and acts like your original drug but is built from a different, cheaper set of ingredients. It's like finding a generic brand of medicine that is chemically similar to the expensive name-brand one.

• Job B: The "Property Optimizer" (Making Better Drugs)

  • Scenario: You want a drug that kills cancer cells but doesn't hurt healthy ones.
  • SynGA's Role: It uses a "smart filter" (called a Neural Additive Model) to guess which ingredients will lead to a high-scoring drug. It then uses the genetic algorithm to mix and match these ingredients to find the perfect recipe. It's like a chef trying to perfect a recipe by only using the highest-rated spices.

Why is this a Big Deal?

• No "Unrealistic" Dreams: Unlike other AI that suggests impossible molecules, SynGA guarantees that everything it suggests can actually be built in a real lab.
• Speed & Efficiency: By filtering out useless ingredients early, it finds good solutions much faster than trying to search the whole universe of possibilities.
• The "Best of Both Worlds": It combines the raw power of evolutionary search (trying millions of combinations) with the smarts of modern AI (knowing which ingredients are relevant).

In a nutshell: SynGA is a practical, recipe-following AI that helps chemists design new drugs by ensuring every idea it generates is something they can actually cook up in the lab, saving time, money, and frustration.

Technical Summary

1. Problem Statement

Molecular design is a constrained optimization problem characterized by a vast, discrete combinatorial space and the critical requirement for synthesizability.

• The Challenge: Many state-of-the-art machine learning (ML) generative models (e.g., VAEs, GFlowNets, LLMs) are "synthesis-agnostic," often proposing molecules that are unstable or impossible to synthesize. Post-hoc filtering via retrosynthesis models is computationally expensive (minutes per evaluation) and often acts as a bottleneck.
• The Gap: While Genetic Algorithms (GAs) are known for sample efficiency and exploration, classical GAs operating on molecular graphs or SMILES strings do not inherently guarantee synthesizability. Existing synthesis-aware methods often rely on training heavy ML projection models to map arbitrary molecules back to synthesizable space, incurring upfront training costs and inference latency.
• Goal: Develop a lightweight, sample-efficient method that navigates molecular space while explicitly enforcing synthesizability by construction, without relying on heavy post-hoc projection models.

2. Methodology: SynGA

The authors propose SynGA, a genetic algorithm that operates directly over synthesis trees rather than molecular graphs or strings.

A. Representation: Synthesis Trees

Instead of representing molecules as SMILES or graphs, SynGA represents a molecule as an unordered binary tree:

• Leaves: Purchasable building blocks ($B$).
• Internal Nodes: Reaction templates ($R$) from a fixed catalog.
• Root: The final product molecule.
• Constraint: A tree is valid only if the reaction at an internal node can chemically combine the products of its children. This structure ensures that every generated molecule has a valid, executable synthesis route by definition.

B. Custom Genetic Operators

SynGA introduces novel crossover and mutation operators tailored to the tree structure:

1. Crossover: Selects compatible subtrees from two parent trees and fuses them using a random compatible reaction. This mimics the fusion of molecular fragments.
2. Mutation: Randomly applies one of five operations:
   • Grow: Adds a new reaction and building block to the root.
   • Shrink: Removes a subtree, replacing the root with one of its children.
   • Rerun: Keeps the topology (blocks/reactions) fixed but reassigns intermediate products (resolving ambiguity in multi-product reactions).
   • Change Internal: Swaps a reaction template at an internal node.
   • Change Leaf: Swaps a building block at a leaf node.

C. Fitness Functions

SynGA supports two primary tasks under a unified framework:

• Property Optimization: Maximizing a specific property (e.g., docking score, QED).
• Analog Search: Maximizing similarity to a query molecule.

D. ML-Guided Enhancements

To boost performance, SynGA integrates lightweight ML components:

1. Building Block Filtering (Analog Search): A binary classifier (MLP) predicts whether a building block can produce an analog of a query molecule. This filters the massive block catalog (200k+) down to a relevant subset, drastically reducing the search space.
2. Neural Additive Models (NAM) for Property Optimization: For property optimization, where explicit goal states are unknown, a NAM is trained to predict property scores based on the sum of block-wise scores. This provides an interpretable prior for filtering blocks.
3. SynGBO (SynGA + Bayesian Optimization): For sample-efficient property optimization, SynGA is embedded as the inner loop of a Bayesian Optimization (BO) framework. The BO loop uses a Gaussian Process (GP) surrogate and the NAM filter to guide SynGA toward high-reward regions, effectively combining the global search of GAs with the sample efficiency of BO.

3. Key Contributions

1. SynGA Algorithm: A simple, ML-free genetic algorithm that operates directly on synthesis trees, guaranteeing 100% validity of generated routes by construction.
2. Hybridization Strategy: An elegant method to enhance SynGA via block filtering.
   • For analog search: A classifier filters blocks based on query similarity.
   • For property optimization: A Neural Additive Model (NAM) filters blocks based on predicted property contributions.
3. SynGBO: A model-based variant that couples SynGA with Bayesian Optimization, achieving state-of-the-art (SOTA) performance in sample-efficient optimization.
4. Comprehensive Benchmarks: Extensive evaluation on 2D (similarity, property) and 3D (docking) objectives, demonstrating that SynGA and SynGBO outperform or compete with complex, synthesis-aware deep learning models.

4. Experimental Results

A. Synthesizable Analog Search

• Task: Find synthesizable analogs for 1,000 molecules from ChEMBL.
• Performance: SynGA with MLP filtering achieved 100% validity (by design) and competitive similarity scores (Morgan, Scaffold, Gobbi) compared to SOTA models like SynFormer and ChemProjector.
• Efficiency: While SynGA is slower in wall-clock time than amortized inference models (due to search), it is significantly more flexible and requires no expensive training phase for new building block sets.

B. Property Optimization (PMO Benchmark)

• Task: Practical Molecular Optimization (PMO) benchmark with 23 tasks.
• Results:
  • Standard SynGA was competitive with other synthesis-aware methods but lagged behind synthesis-agnostic methods (due to the constrained search space).
  • SynGBO (SynGA + BO) achieved SOTA performance, outperforming both synthesis-aware and synthesis-agnostic baselines (e.g., f-RAG, GPBO, MolGA) with a total AUC of 16.426 (vs. 16.304 for GPBO).

C. 3D Docking Optimization

• Task: Optimize Vina docking scores for LIT-PCBA receptors.
• Results: SynGA achieved better docking scores than all synthesis-aware baselines (SynNet, BBAR, GFlowNets) using only 25% of the oracle calls (16k vs. 64k).
• SynGBO: Further improved docking scores, surpassing even the 3D-aware method 3DSynthFlow in several metrics, demonstrating the power of combining GA exploration with ML guidance.

5. Significance and Conclusion

• By-Construction Synthesizability: SynGA eliminates the "validity gap" common in generative models. Every output is a valid synthesis plan, removing the need for expensive post-hoc validation.
• Lightweight & Modular: Unlike heavy deep learning models, SynGA is computationally lightweight and can be easily integrated into larger workflows or combined with other ML techniques (e.g., as a subroutine in BO).
• Sample Efficiency: The combination of GAs (for exploration) and ML filters/BO (for exploitation) creates a highly sample-efficient system, crucial for expensive experimental validation loops.
• Versatility: The framework successfully handles both 2D similarity tasks and complex 3D docking tasks, proving that synthesis constraints do not necessarily hinder performance in high-dimensional optimization problems.

In summary, SynGA demonstrates that classical evolutionary algorithms, when properly adapted to the domain constraints of chemistry (synthesis trees), remain a powerful and competitive tool for molecular design, especially when augmented with lightweight, interpretable ML components.