Rapid Exploration of the Assembly Chemical Space of Molecular Graphs

Quantifying how hard it is to build a molecular graph matters for biosignature detection, chemical complexity, and cheminformatics. We present an exact, scalable algorithm to compute the molecular assembly index (MA), which prioritizes the largest duplicate subgraphs, represents fragmentation with an array of edge-lists, and prunes the search with both dynamic programming via a hash table of assembly states and a branch-and-bound heuristic guided by a conditional addition-chain lower bound. For organic molecules in the greater-than-500 Da range, our approach is up to 6 orders of magnitude faster than prior methods and yields exact MAs where previous algorithms would have timed out. We compute MAs to convergence for ∼300k COCONUT natural products with <50 bonds, profiling time and memory scaling. Finally, we exploit the speed of our algorithm to calculate joint assembly spaces and introduce the Joint Assembly Overlap (JAO), a Jaccard-like metric that emphasizes global scaffold reuse, and show that the JAO yields substantially different rankings from Tanimoto similarity with ECFP fingerprints and MCS (e.g., in steroids 270–380 Da and short peptides), accounting for substructural similarity beyond local environments. Together, these advances turn the molecular assembly index into a practical tool for large-scale exploration of chemical space.