SMSD Pro: Coverage-Driven, Tautomer-Aware Maximum Common Substructure Search
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
Maximum common substructure (MCS) search is foundational to scaffold hopping, matched molecular pair analysis, and reaction mapping. However, the problem's inherent NP-hardness often necessitates time-constrained heuristics, which can introduce variance into computational pipelines. We introduce a label-frequency upper bound (LFUB) that provides a time-independent certificate of MCS optimality, reducing the need for arbitrary timeouts. We further define tautomeric equivalence classes with pKa-informed relevance weights that recover pharmacophoric overlap across tautomeric shifts, bypassing the combinatorial overhead of O(2κ) pre-generation (where κ is the number of tautomeric sites). Supported by fast paths that reduce polymer degeneracy from factorial to O(N ·M) and efficiently resolve branched acyclic structures, the framework achieves a 22x geometric-mean speedup over industry-standard baselines ( e.g., RDKit; range 4.4–8,617x), while recovering up to 11 additional matched atoms in tautomer-sensitive systems. Source code is available at https://github.com/asad/SMSD .
Fields of Study & Subjects
Computational Drug Discovery Methods
Graph Theory and Algorithms
Graph theory and applications
Publication details
- Journal / source
- ChemRxiv
- Publication date
- 2 April 2026
- Language
- EN
- Document type
- Preprint