Rapid Exploration of the Assembly Chemical Space of Molecular Graphs.

ABSTRACT: 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 sc

SUBMITTER: Seet I 

PROVIDER: S-EPMC12728931 | biostudies-literature | 2025 Dec

REPOSITORIES: biostudies-literature