Unlock Chemistry: AI Finds Diverse e Complete Synthesis Routes

Hey there! Ever wondered how chemists figure out how to make complicated molecules? It’s not like following a recipe for cookies; it’s more like reverse-engineering a gourmet meal from just the final dish. That process is called retrosynthesis, and it’s been a cornerstone of organic chemistry for decades, ever since folks like Corey kicked it off back in the 60s.

Think of it this way: you have a target molecule you want to build. Retrosynthesis is about breaking it down, step by step, into simpler pieces – building blocks you can actually buy or easily whip up. It’s a bit like dismantling a complex LEGO castle to see which basic bricks you need.

Now, doing this manually? Phew, it’s tough! There are *so* many possible chemical reactions, and you have to juggle a million things: what ingredients are available, protecting sensitive parts of the molecule, safety rules, even being kind to the planet (green chemistry!). Traditionally, this took serious human brainpower and years of experience.

But guess what? Computers are getting pretty darn good at helping out. Over the last ten years, the field of Computer-Assisted Synthesis Planning (CASP) has exploded, thanks to clever machine learning and finally having enough data on chemical reactions to train these digital brains.

There are a couple of main ways these CASP tools work. Some use “templates,” which are basically pre-defined patterns for how specific parts of molecules react. Experts or data can pull these out. Others are “template-free,” more like translating one set of chemical “words” (the starting stuff) into another (the product), often using techniques borrowed from how computers handle human languages. Both approaches, when hooked up to smart search algorithms, can find synthesis routes.

Back in 2018, some clever folks showed you could use neural networks – a type of AI – to predict which reaction patterns were most likely to work and how good they were. Since then, tons of research has focused on making these AI models better.

But here’s the thing: finding *a* synthesis plan is one challenge. Finding a *good* one? That’s another story. What “good” even means changes depending on the situation. Are you in a big pharma lab, a small university setting, or trying to make something on a massive industrial scale? Safety, yield (how much stuff you get), required skills, equipment – they all matter differently. It’s super hard to write a single, formal definition of “quality.”

The Quest for Quality Through Diversity

So, we decided to tackle this from a different angle. Instead of trying to define one perfect plan, we thought: why not find *lots* of different plans? Our approach boils down to quality through diversity. If we give chemists a whole bunch of options, they can look at the set and pick the one (or even combine ideas from several) that best fits their specific needs right now.

This diversity is totally possible because, over 250 years of chemistry, people have figured out tons of ways to make the same molecule! The challenge isn’t that the options don’t exist; it’s that there are *too many* options. In every single step of breaking down the molecule, you might have a massive number of possible reactions to choose from. Exploring all those possibilities to find even one route is hard enough, let alone finding a whole diverse collection.

Lots of algorithms have been proposed to navigate this chemical maze, some even treating retrosynthesis like a two-player game (more on that in a bit!). A popular one is called Monte-Carlo Tree Search (*MCTS*). It’s good at finding multiple solutions if you let it run for a while, but it doesn’t necessarily guarantee that the solutions it finds are truly *different* from each other in a meaningful chemical way.

Instead of *MCTS*, we looked at something called Depth-First Proof-Number Search (*DFPN*). It’s a more efficient variation of another algorithm called Proof-Number Search (*PNS*). *DFPN* has been used for retrosynthesis before, but typically, these algorithms stop once they find the *first* solution. That’s not what we want if we’re aiming for diversity!

So, we developed an adaptation – something you could add to pretty much any version of *PNS* – that makes it output a *set* of solutions, with a specific focus on making that set diverse.

We also tackled a bit of an open puzzle about *DFPN* itself. It was known that the basic *DFPN* algorithm isn’t “complete.” What that means in computer science talk is that even if a solution *exists*, the algorithm might get stuck in an infinite loop and never find it. Not ideal! While some tweaks seemed to fix this in practice, there wasn’t a formal proof that they guaranteed completeness. We managed to provide that proof for *DFPN* combined with a technique called the Threshold Controlling Algorithm (*TCA*).

In our work, we first dive into how we measure diversity (it’s trickier than it sounds!), then how we frame retrosynthesis as a game, how algorithms like *DFPN* play that game, and finally, how we tweaked *DFPN* to find those lovely diverse sets of solutions.

Measuring Chemical Diversity: More Than Just Counting

Okay, let’s talk about measuring diversity. Chemists have a pretty good feel for what makes synthesis routes chemically different. But trying to write that down formally, in a way a computer can understand? That’s a challenge. Still, if we’re going to build CASP tools that prioritize diversity, we need a way to measure it objectively, not just rely on gut feelings.

People have tried different things before. You could try measuring how different the molecules involved in the routes are, or just count how many unique intermediate molecules or starting materials pop up. We looked at these kinds of numbers, but they’re not always the best. Why? Because small changes in a molecule that don’t really affect the core chemical reaction (like different protective groups) can make routes look structurally different when they’re actually using the same basic chemistry.

Another idea is to compare the routes like complex graphs and measure the “distance” between them. You could then cluster similar routes together to see how diverse the overall set is. This is a step up, focusing more on the relevant differences. But it has its own issues. Sometimes, adding *more* routes to a set could actually make the calculated diversity score go *down*, which feels counter-intuitive if your goal is to give chemists more options. Plus, the mathematical distance might not care about what a chemist considers a *chemically* important difference.

A really strict way is just to count routes that have *zero* overlap in reactions. But that’s too harsh! It might miss out on great chemical ideas just because they share one common step with another route.

We worked closely with experienced lab chemists from different areas – medicine, agriculture, industry – to figure out what “diversity” really means to them. The consensus was: it’s about the number of different *chemical ideas* used across the synthesis pathways. The problem is, “chemical idea” is just as vague as “diversity”!

So, we proposed a new metric we call the Chemical Diversity Score (CDS). It’s based on the intuitive idea of “disconnections” – basically, which bonds are broken (or formed, if you think forward) in each step of the retrosynthesis. This mimics how chemists often think when planning. By looking at the unique sets of bond disconnections across a set of routes, we can track the different synthesis strategies being used.

We decided to focus our diversity measure on the final output – the complete synthesis routes – rather than trying to measure diversity at intermediate steps or within the AI models themselves. Why? Because the final set of routes is what the chemist actually sees and uses. Plus, we found that having a diverse set of predicted reactions doesn’t always translate into a diverse set of final routes; other parts of the process, like filtering or the search algorithm, can wash that diversity away.

The CDS works by identifying all the bonds formed in the forward direction for each pathway. Then, it finds the unique, essential sets of these bond formations across all pathways. We eliminate reactions that don’t add a new “chemical idea.” The final score is a number that roughly tells you how many distinct chemical ideas are present. A higher CDS means more diversity – exactly what we want! For example, there are like 20 variations of the famous Suzuki coupling reaction, all doing essentially the same thing (making a specific type of carbon-carbon bond). Our CDS, by focusing on the disconnection, would see these as the same core idea, which aligns with how chemists think about strategy.

Retrosynthesis as a Game

Okay, how do you turn this into something an algorithm can chew on? A standard way is to see retrosynthetic planning as a game played on a graph. Imagine a network where some points (nodes) are molecules and others are reactions. We can think of it as a two-player game with a “molecule player” and a “reaction player.”

You start at the node for your target molecule. If it’s a molecule node, it’s the molecule player’s turn. They can move to any reaction node that produces that molecule. If it’s a reaction node, it’s the reaction player’s turn. They move to the nodes representing the starting materials (reactants) needed for that reaction.

The molecule player wins if they reach a node representing a building block that’s readily available (like, you can just buy it). The reaction player wins if they hit a dead end (a molecule you can’t make or buy) or if the game gets stuck in a loop, visiting the same node twice in the same path.

So, a winning strategy for the molecule player is essentially a valid synthesis plan! If the reaction player has a winning strategy, it means that molecule can’t be made using the reactions in your graph. Algorithms like *PNS* and *DFPN* are designed to find winning strategies in these kinds of games.

There’s also a one-player version where nodes are sets of molecules, and edges are reactions that transform one set into another. *MCTS* often works on this type of game. It explores by picking promising nodes, expanding them, simulating a game from there, and then updating its knowledge based on the outcome. If you run *MCTS* for a long time, it tends to explore different paths and can find multiple solutions, but again, without an explicit focus on chemical diversity.

The Algorithms: PNS, DFPN, and the Completeness Challenge

Let’s zoom in on *PNS* and *DFPN*. *PNS* explores the game graph by keeping track of “proof numbers” and “disproof numbers” for each node. These numbers are estimates of how many unexplored nodes you’d need to prove (show they lead to building blocks) or disprove (show they lead to dead ends) to prove or disprove the current node. *PNS* always picks the “most promising” node to explore next based on these numbers. It’s exact on simple tree-like graphs, but real chemical space is a tangled mess with cycles!

*DFPN* is a more efficient version because it doesn’t restart the search for the most promising node from the beginning every time. It uses thresholds to decide whether to keep going down a path or backtrack. It’s faster, but as we mentioned, the basic version isn’t “complete” on general graphs – it can get stuck in those infinite loops.

This “Graph History Interaction Problem” is tricky. If you visit the same molecule node through two different sequences of reactions, the proof or disproof status might depend on the *path* you took. You can’t always just reuse information. Solutions exist, like keeping track of the path history, but it adds complexity.

Solving the Completeness Puzzle

To break those infinite loops and make *DFPN* complete, the Threshold Controlling Algorithm (*TCA*) comes into play. *TCA* keeps track of how far each node is from the start. If *DFPN* is about to backtrack because a threshold isn’t met, but it’s looking at a node that’s “old” (meaning it’s closer to the start or already visited via a shorter path), *TCA* forces the thresholds to be adjusted so *DFPN* keeps exploring. It’s like saying, “Hey, don’t give up on this path just yet, you might be in a loop, but there’s progress to be made here.”

We actually found a much simpler example than previously known to show exactly how basic *DFPN* gets stuck in an infinite loop, visiting the same few nodes over and over and missing the actual solution. Our example only needed 7 nodes, compared to 17 in the old one! We showed how *TCA* would step in in our simple example, adjust the thresholds, force the algorithm to explore the missing node, and find the solution.

And the big news here is that we provide a formal proof that *DFPN* combined with *TCA* *is* complete. If a solution exists, this algorithm *will* find it eventually. Our proof shows that even if the algorithm seems stuck, the “inconsistency” in its proof/disproof numbers (which is what causes the loops) actually decreases over time in a structured way, guaranteeing it will eventually break free.

Introducing DFPN*: Finding Diverse Solutions

Since the basic algorithms only find one solution and are deterministic (run it twice, get the same result), we had to modify *DFPN* to get that diversity we’re after. Our new algorithm is called DFPN*.

The core idea for finding multiple solutions is to find one winning strategy (a synthesis route), and then somehow tell the algorithm to ignore parts of that solution so it’s forced to look for a different one. We do this by changing the proof/disproof numbers for certain nodes in the found route, essentially making that path look less appealing or even “invalid” for the next search run.

We have to be smart about which nodes we mess with. The choice affects the kind of diversity we get. We also need to handle the Graph History Interaction Problem – if the algorithm revisits a node it previously “invalidated” via a *different* path, it should still be allowed to use it. So, we keep track of the path used to reach a node.

To really encourage diversity, we penalize nodes that are part of a found winning strategy. Specifically, we add a penalty to the “proof number” of reaction nodes along the successful path. Adding penalties to molecule nodes would also work, but penalizing the reaction is more direct, as disproving a molecule node often just leads to disproving the reaction that produces it anyway. We can adjust the size of these penalties – higher penalties push the algorithm to find more diverse routes, but it might take longer.

Our *DFPN** algorithm is built on a version of *DFPN* called *DFPN-E*, which uses heuristics (smart guesses) to estimate the “cost” of using a particular reaction step. We then layer our diversity strategy on top. We found that disproving a reaction that’s “deepest” in the found route (farthest from the target molecule) is a good way to force the algorithm to look for shorter routes without wiping out too many possibilities overall.

Putting it to the Test: DFPN* vs. MCTS

So, how does *DFPN** stack up? We compared it to an *MCTS* implementation using a set of 1000 test molecules. One common metric is simply how many molecules an algorithm can find a route for. This depends a lot on the database of available starting materials, so direct comparisons across different studies are hard. But comparing our *DFPN** to our *MCTS* implementation, we saw that *DFPN** found routes for slightly more molecules, especially with shorter search times (like 60 to 300 seconds). For longer times (600-1200 seconds), both algorithms found routes for about 94% of the molecules, pretty similar performance there.

But the *main* thing we cared about was diversity, measured by our Chemical Diversity Score (CDS). And here, *DFPN** really shines! For *MCTS*, the median CDS was never much higher than 2, no matter how long we let it run. This means the typical set of routes found by *MCTS* only contained about 2 distinct chemical ideas.

For *DFPN**, the median CDS started at 2 for short search times but climbed significantly, reaching a plateau around 3.8 for longer times. Even the lower end of the middle 50% of *DFPN**’s results (the lower IQR) was consistently above the *median* CDS for *MCTS*. Looking at the best results (the “whiskers” on the plot), *DFPN** hit CDS values around 9, while *MCTS* topped out around 6.

What this tells us is that *MCTS*, even when finding more routes over time, seems to keep exploring variations of the same basic chemical ideas. *DFPN**, on the other hand, actively seeks out and finds genuinely different synthesis strategies.

We also looked at the length of the routes (average number of reactions). For very short search times, *MCTS* found slightly shorter routes on average. But as search time increased, the average route length for *MCTS* grew much faster than for *DFPN**. This suggests *MCTS* finds the shortest routes first, then tends to just deepen those same paths. *DFPN** seems to find a mix of route lengths from the start and continues to find shorter ones even later in the search, indicating it’s exploring a wider range of possibilities.

We also briefly looked at “route viability” – an estimate of how likely a route is to work in the lab, based on a predictive model. This metric has caveats because the models aren’t perfect (especially with limited data on reactions that *failed*). But generally, longer routes tend to have lower viability scores because you multiply probabilities for each step. *DFPN** had slightly lower viability scores at short times (likely due to finding a mix of lengths), but for longer times, it actually showed higher average viability than *MCTS*. This might be because *MCTS* tends to favor reactions the model scores highly, which limits diversity, while *DFPN** is willing to explore paths with slightly lower-scoring reactions to find diverse ideas, but its overall strategy leads to viable options. We consciously designed *DFPN** not to blindly trust the reaction prediction model but to use it efficiently while still exploring broadly. We think the trade-off for increased diversity is totally worth it.

Why Diversity Wins: The Future of CASP

So, what’s the takeaway? We’ve adapted the *DFPN* algorithm to find multiple synthesis solutions for chemical retrosynthesis, making diversity our top priority with our *quality through diversity* principle. We introduced a new way to measure this diversity, the Chemical Diversity Score (CDS), based on unique chemical ideas (disconnections).

When we put *DFPN** head-to-head with *MCTS*, *DFPN** performed comparably or slightly better on the number of molecules solved, but it was clearly superior in generating chemical diversity and finding routes with a better mix of lengths, especially as search time increased.

This work tackles two big issues with current CASP tools. First, the AI models aren’t perfect, so relying on just one “optimal” route they suggest is risky. Second, what’s “optimal” varies wildly depending on the chemist’s specific situation. The best way around both is to offer a *diverse set* of high-quality options. Users can then pick the pathways that make the most sense for their lab, equipment, and goals.

We believe *DFPN** helps make CASP tools more useful and user-friendly by providing these highly diverse pathways without sacrificing individual route quality.

Looking ahead, this focus on diversity opens up cool possibilities. Imagine searching a database of potential drug molecules not just for activity, but also for which ones can be made using similar, overlapping synthesis routes. Finding candidates that share reactions, intermediates, or starting materials could massively reduce the effort and cost of making them in the lab. High chemical diversity in the generated routes is essential to even *find* these overlapping sets.

Right now, our computation runs on a single processor core, which means users might have to wait. Getting this to run across multiple cores on modern computers would speed things up a lot and make it much smoother to integrate into daily lab work.

Ultimately, it’s exciting to see how algorithms can not only help chemists plan but also offer them a richer, more useful set of options to choose from.

Source: Springer