AND-OR Tree Search

An AND node represents a reaction step where all child precursors must be successfully synthesized for the parent molecule to be accessible. This models the conjunctive nature of bimolecular reactions.

• If a reaction requires two reactants (A + B → Target), both A and B must be independently synthesizable.
• Failure to synthesize any single child propagates failure upward through the tree.
• This enforces convergent synthesis constraints, where multiple branches must be solved simultaneously.
• In cost-aware search, the cost of an AND node is typically the sum of its children's costs plus the reaction cost.

An OR node represents a molecule that can be synthesized through any one of several alternative disconnections. Only one viable pathway needs to succeed.

• If a target can be made via a Grignard reaction OR a Suzuki coupling, these are OR children.
• The search algorithm explores alternatives until one succeeds or all are exhausted.
• In cost-optimized planning, the OR node selects the minimum cost child pathway.
• This structure naturally encodes the chemical reality that most molecules have multiple viable synthetic routes.

The tree is constructed by recursively applying retrosynthetic transforms until all leaf nodes are commercially available building blocks.

• Starting from the target molecule (root), each disconnection generates precursor nodes.
• Precursors become new subgoals, which are themselves decomposed.
• Recursion terminates when a molecule is found in the building block library.
• The depth of recursion corresponds to the longest linear sequence in the synthetic route.
• Unbounded recursion is prevented by setting a maximum search depth parameter.

AND-OR trees are typically traversed using heuristic search algorithms that balance exploration and exploitation under resource constraints.

• Monte Carlo Tree Search (MCTS) uses random rollouts and backpropagation to estimate node values without exhaustive enumeration.
• Best-first search expands the most promising node according to a heuristic function (e.g., Synthetic Accessibility Score).
• Proof-number search is specialized for AND-OR trees, computing the minimum number of leaf nodes that must be examined to prove or disprove the root.
• The branching factor in retrosynthesis is extremely high, making exhaustive search computationally intractable.

Cost values flow from leaves to root according to node-type-specific aggregation rules, enabling global route optimization.

• AND node cost = sum of children's costs + reaction step cost (yield penalty, reagent expense).
• OR node cost = minimum of children's costs.
• This bottom-up propagation allows the root node's cost to reflect the optimal synthetic route.
• Dynamic programming techniques can cache subproblem solutions to avoid redundant computation when the same intermediate appears in multiple branches.

An AND-OR tree is the logical problem-solving structure, while a retrosynthetic tree is the instantiation populated with actual molecules and reactions.

• Each node in a retrosynthetic tree is a specific molecule (represented as a SMILES string or molecular graph).
• Each edge is a specific reaction with atom mapping and conditions.
• The AND-OR structure constrains which combinations of reactions form valid pathways.
• A solved AND-OR tree yields one or more complete synthetic routes from commercially available materials to the target.

A hierarchical data structure where the root node is the target molecule and child nodes represent precursor molecules. Edges correspond to chemical reactions. The tree grows recursively until all leaf nodes are commercially available building blocks. Key properties include:

• Depth: Number of synthetic steps from target to starting materials
• Branching factor: Number of alternative disconnections at each node
• Convergent vs. linear: Whether fragments are synthesized independently and coupled late-stage

A synthetic strategy where multiple molecular fragments are synthesized independently in parallel and then coupled together at a late stage. In AND-OR tree search, convergent routes produce shallower trees with higher branching factors. This is preferred over linear synthesis because:

• Overall yield is multiplied across fewer sequential steps
• Parallel synthesis reduces total calendar time
• Late-stage diversification enables analog library generation

A curated catalog of commercially available or in-stock compounds that serve as terminal nodes in the retrosynthetic tree. When the search algorithm reaches a molecule present in this library, it stops recursing on that branch. Key considerations:

• Availability: In-stock vs. catalog-only compounds
• Cost: Price per gram influences route economics
• Diversity: Coverage of chemical space affects solve rates
• Popular libraries include eMolecules, Enamine REAL, and Sigma-Aldrich catalogs

A planning strategy that optimizes synthetic routes not just for feasibility but also for economic viability. The cost function integrates:

• Starting material cost from building block catalogs
• Reagent and catalyst costs per reaction step
• Estimated yield at each transformation
• Step count as a proxy for labor and time This transforms the search from a binary feasibility problem into a multi-objective optimization over both chemistry and economics.

A training paradigm where an agent learns a policy to select disconnections by maximizing a cumulative reward signal. The reward function typically encodes:

• Route validity: Penalty for chemically infeasible steps
• Convergence: Bonus for reaching building blocks quickly
• Route quality: Weighted score combining step count, yield estimates, and cost Unlike supervised learning on historical reactions, RL can discover novel disconnection strategies not present in training data through exploration.