FragmentRetro: A Quadratic Retrosynthetic Method Based on Fragmentation Algorithms

Yu Shee, Anthony M. Smaldone, Anton Morgunov, Gregory W. Kyro, Victor S. Batista · 2025

Read FragmentRetro: A Quadratic Retrosynthetic Method Based on Fragmentation Algorithms by Yu Shee, Anthony M. Smaldone, Anton Morgunov, Gregory W. Kyro, Victor S. Batista (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-15409.txt.

Introduction

Yu Shee leads a team that plans how to build a target molecule from simpler parts. This backward planning, called retrosynthesis, guides computer aided chemical design. The common tree search method can blow up in cost as molecules grow. The team wanted a method whose cost grows far more slowly.

Their method, FragmentRetro, breaks the target with known cutting rules, then joins the pieces back in ways that match a stock of real building blocks. They give the first formal cost study of such methods and show theirs grows with the square of size, not far faster. Tests on three data sets show high success rates and good speed. The method solves some cases where tree search fails.

Catalog record

CREATORYu Shee, Anthony M. Smaldone, Anton Morgunov, Gregory W. Kyro, Victor S. Batista
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-15409

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

FragmentRetro: A Quadratic Retrosynthetic Method Based on Fragmentation Algorithms Yu Shee, Anthony M. Smaldone, Anton Morgunov, Gregory W. Kyro, Victor S. Batista Abstract Retrosynthesis, the process of deconstructing a target molecule into simpler precursors, is crucial for computer-aided synthesis planning (CASP). Widely adopted tree-search methods often suffer from exponential computational complexity. In this work, we introduce FragmentRetro, a novel retrosynthetic method that leverages fragmentation algorithms, specifically BRICS and r-BRICS, combined with stock-aware exploration and pattern fingerprint screening to achieve quadratic complexity. FragmentRetro recursively combines molecular fragments and verifies their presence in a building block set, providing sets of fragment combinations as retrosynthetic solutions. We present the first formal computational analysis of retrosynthetic methods, showing that tree search exhibits exponential complexity 𝒪 ⁡ ( b h ) \mathcal{O}(b^{h}) , DirectMultiStep scales as 𝒪 ⁡ ( h 6 ) \mathcal{O}(h^{6}) , and FragmentRetro achieves 𝒪 ⁡ ( h 2 ) \mathcal{O}(h^{2}) , where h h represents the number of heavy atoms in the target molecule and b b is the branching factor for tree search. Evaluations on PaRoutes, USPTO-190, and natural products demonstrate that FragmentRetro achieves high solved rates with competitive runtime, including cases where tree search fails. The method benefits from fingerprint screening, which significantly reduces substructure matching complexity. While FragmentRetro focuses on efficiently identifying fragment-based solutions rather than full reaction pathways, its computational advantages and ability to generate strategic starting candidates establish it as a powerful foundational component for scalable and automated synthesis planning. 1 Introduction Figure 1 : The FragmentRetro algorithm. (a) Cartoon representation of an example molecule processed by BRICS or r-BRICS to yield initial fragments labeled A to F. (b) The FragmentRetro process: In Stage 1, all initial fragments have substructure matches in the stock set. In Stage 2, fragments A–B, B–C, and E–F are valid. In Stage 3, only fragment A–B–C remains valid. Fragments like A–B–D do not need to be checked, since B–D is invalid and therefore A–B–D cannot have a substructure match. There is no Stage 4, as no valid combinations of four fragments are possible in this case. (c) Possible solutions are sorted by the number of fragments, with the most efficient solution on the left. (d) Each valid fragment is associated with a subset of the stock that has substructure matches. Retrosynthetic analysis, the deconstruction of a target molecule into simpler, typically commercially available precursors, is fundamental to chemical synthesis and drug discovery [ 1 , 2 ] . Computer-aided synthesis planning (CASP) aims to automate this complex task. A conventional paradigm in CASP involves tree-search algorithms, such as Monte Carlo Tree Search (MCTS) [ 3 ] , A* search (Retro*) [ 4 ] , and Depth-First Proof Number (DFPN) search [ 5 ] . These methods iteratively apply single-step retrosynthetic (SSR) models, often machine learning-based [ 6 , 7 , 8 , 9 ] , to explore the vast combinatorial space of possible synthetic routes. While effective, a primary limitation of such tree-search approaches is their inherent exponential computational complexity with respect to tree depth, which can hinder scalability for large and complex targets. Recent advancements aim to mitigate this, for example, by incorporating graph-based neural networks [ 10 ] , reinforcement learning [ 11 ] , route context [ 12 ] , or higher-level abstractions of molecular features [ 13 ] . However, the underlying exponential scaling often persists in the worst-case scenario. Alternative strategies have emerged to address these scalability challenges. DirectMultiStep (DMS) models, for instance, leverage sequence-to-sequence architectures to generate entire multi-step pathways directly, bypassing iterative search [ 14 ] . While DMS has shown promising performance, particularly on benchmarks like PaRoutes [ 15 ] , and exhibits polynomial complexity, its \mathcal{O}(h^{6}) scaling with molecular size h can still be demanding. Other approaches, such as Double-Ended Synthesis Planning (DESP) [ 16 ] , improve efficiency for specific use cases by conducting a bidirectional tree-search when starting materials are provided by the user, though they still rely on iterative single-step predictions. This landscape motivates the exploration of fundamentally different algorithmic approaches to retrosynthesis that offer improved computational efficiency, particularly for unconstrained initial exploration, without sacrificing solution quality. In this work, we introduce FragmentRetro, a novel retrosynthetic method that adopts a bottom-up, fragment-based strategy (Fig. 1 ). FragmentRetro utilizes molecular fragmentation algorithms (BRICS [ 17 ] and its revision, r-BRICS [ 18 ] ) to decompose a target molecule. It then recursively combines these fragments, systematically verifying if the combined fragments exist as substructures within a provided set of commercially available building blocks (BBs). By integrating efficient substructure matching, augmented by pattern fingerprint and property screening, FragmentRetro identifies sets of fragment combinations that reconstruct the target. A key contribution of this paper is the first formal computational complexity analysis comparing these distinct retrosynthetic paradigms. We demonstrate that while tree-search methods scale exponentially ( \mathcal{O}(b^{h}) ) and DMS polynomially ( \mathcal{O}(h^{6}) ), FragmentRetro achieves a significantly more favorable quadratic complexity ( \mathcal{O}(h^{2}) ), albeit with a linear dependency on the stock set size which is effectively managed through parallelization. We evaluate FragmentRetro on established benchmarks, including PaRoutes and USPTO-190, as well as challenging natural products. Our results show that FragmentRetro, particularly when using r-BRICS, achieves high solved rates, competitive with or exceeding those of tree-search and DMS methods in certain scenarios, often with substantially reduced runtimes. For instance, on USPTO-190 with a large BB set, FragmentRetro with r-BRICS attains the highest solved rate (78.4%) and demonstrates excellent parallelization for substructure matching. While FragmentRetro currently outputs sets of reconstructive fragments rather than fully elaborated reaction pathways in the form of directed acyclic graphs (DAGs), it provides a computationally efficient and scalable foundation for identifying viable precursor sets. This positions it as a powerful tool for initial synthesis exploration, potentially complementing other methods in a tiered approach to retrosynthesis. Our main contributions are: (1) the FragmentRetro algorithm, a novel fragment-based retrosynthetic method with quadratic complexity; (2) a comprehensive computational complexity analysis of major retrosynthetic paradigms; and (3) empirical validation demonstrating FragmentRetro’s competitive performance and scalability. 2 Related work The automation of retrosynthetic analysis has been a long-standing goal, evolving from rule-based systems to sophisticated machine learning-driven approaches. Understanding this landscape highlights the unique positioning of FragmentRetro. 2.1 Tree-search based retrosynthesis The predominant approach to CASP involves constructing a search tree or graph. Early systems relied on expert-defined chemical rules [ 1 ] . Modern methods typically integrate machine learning models for SSR predictions with advanced search algorithms. These SSR models can be template-based, utilizing predefined reaction patterns [ 6 , 19 , 7 , 8 , 20 , 21 , 22 , 9 , 23 ] , or template-free, directly predicting reactants from products [ 24 ] . Popular search algorithms include Monte Carlo Tree Search (MCTS) [ 3 , 25 ] , A* search Retro* [ 4 ] , and Proof-Number Search derivatives like DFPN [ 5 ] . Recent advancements in tree search focus on improving efficiency and prediction quality. For example, Xie et al. 2022 proposed RetroGraph, using graph neural networks to guide search on an explicit graph representation of intermediates to avoid redundant computations [ 10 ] . Reinforcement learning techniques, such as in GRASP [ 11 ] ,

Read the complete text