Efficient Heuristics for Maximum Common Substructure Search

Englert, Péter; Kovács, Péter

doi:10.1021/acs.jcim.5b00036

Cited by 37Computational Drug Discovery MethodsGraph Theory and AlgorithmsGraph theory and applications

Efficient Heuristics for Maximum Common Substructure Search

Englert, Péter, Kovács, Péter·2015·Journal of Chemical Information and Modeling

DOI 10.1021/acs.jcim.5b00036

Open this paper in CoChat — free account

Abstract

Maximum common substructure search is a computationally hard optimization problem with diverse applications in the field of cheminformatics, including similarity search, lead optimization, molecule alignment, and clustering. Most of these applications have strict constraints on running time, so heuristic methods are often preferred. However, the development of an algorithm that is both fast enough and accurate enough for most practical purposes is still a challenge. Moreover, in some applications, the quality of a common substructure depends not only on its size but also on various topological features of the one-to-one atom correspondence it defines. Two state-of-the-art heuristic algorithms for finding maximum common substructures have been implemented at ChemAxon Ltd., and effective heuristics have been developed to improve both their efficiency and the relevance of the atom mappings they provide. The implementations have been thoroughly evaluated and compared with existing solutions (KCOMBU and Indigo). The heuristics have been found to greatly improve the performance and applicability of the algorithms. The purpose of this paper is to introduce the applied methods and present the experimental results.

Integrity signals

Registry

Crossref · 10.1021/acs.jcim.5b00036

Cites

55 of 55 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Untitled work
(1979) · Cited by 43,841 · see citing works
The Protein Data Bank
Berman, H. M. (2000) · Nucleic Acids Research · doi:10.1093/nar/28.1.235 · Cited by 40,196 · see citing works
Extended-Connectivity Fingerprints
Rogers, D. O. W., & Hahn, M. (2010) · Journal of Chemical Information and Modeling · doi:10.1021/ci100050t · Cited by 7,597 · see citing works
GRAPH THEORY
Harary, F. (1969) · doi:10.21236/ad0705364 · Cited by 4,868 · see citing works
Chemical Similarity Searching
Willett, P., Barnard, J. M., & Downs, G. M. (1998) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci9800211 · Cited by 1,775 · see citing works
The Generation of a Unique Machine Description for Chemical Structures-A Technique Developed at Chemical Abstracts Service.
Morgan, H. L. (1965) · Journal of Chemical Documentation · doi:10.1021/c160017a018 · Cited by 1,716 · see citing works
THIRTY YEARS OF GRAPH MATCHING IN PATTERN RECOGNITION
Conte, D., Foggia, P., Sansone, C., & Vento, M. (2004) · International Journal of Pattern Recognition and Artificial Intelligence · doi:10.1142/s0218001404003228 · Cited by 1,373 · see citing works
Concepts and applications of molecular similarity
Johnson, M. A., & Maggiora, G. M. (1990) · Wiley eBooks · Cited by 1,322 · see citing works
The worldwide Protein Data Bank (wwPDB): ensuring a single, uniform archive of PDB data
Berman, H. M., Henrick, K., Nakamura, H., & Markley, J. L. (2006) · Nucleic Acids Research · doi:10.1093/nar/gkl971 · Cited by 1,124 · see citing works
Congruent Graphs and the Connectivity of Graphs
Whitney, H. (1932) · American Journal of Mathematics · doi:10.2307/2371086 · Cited by 867 · see citing works
A graph distance metric based on the maximal common subgraph
Bunke, H., & Shearer, K. (1998) · Pattern Recognition Letters · doi:10.1016/s0167-8655(97)00179-7 · Cited by 763 · see citing works
Maximum common subgraph isomorphism algorithms for the matching of chemical structures
Raymond, J. W., & Willett, P. (2002) · Journal of Computer-Aided Molecular Design · doi:10.1023/a:1021271615909 · Cited by 428 · see citing works
Why do we need so many chemical similarity search methods?
Sheridan, R. (2002) · Drug Discovery Today · doi:10.1016/s1359-6446(02)02411-x · Cited by 412 · see citing works
Annual Reports in Computational Chemistry
(2009) · Annual reports in computational chemistry · doi:10.1016/s1574-1400(09)00513-1 · Cited by 386 · see citing works
Feature trees: A new molecular similarity measure based on tree matching
Rarey, M., & Dixon, J. S. (1998) · Journal of Computer-Aided Molecular Design · doi:10.1023/a:1008068904628 · Cited by 329 · see citing works
RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs
Raymond, J. W. (2002) · The Computer Journal · doi:10.1093/comjnl/45.6.631 · Cited by 321 · see citing works
Backtrack search algorithms and the maximal common subgraph problem
McGregor, J. J. (1982) · Software Practice and Experience · doi:10.1002/spe.4380120103 · Cited by 299 · see citing works
Molecular Similarity in Drug Design
Dean, P. M. (1995) · Springer eBooks · doi:10.1007/978-94-011-1350-2 · Cited by 293 · see citing works
Enumerating all connected maximal common subgraphs in two graphs
Koch, I. (2001) · Theoretical Computer Science · doi:10.1016/s0304-3975(00)00286-3 · Cited by 245 · see citing works
A note on the derivation of maximal common subgraphs of two directed or undirected graphs
Levi, G. (1973) · CALCOLO · doi:10.1007/bf02575586 · Cited by 237 · see citing works
A maximum common substructure-based algorithm for searching and predicting drug-like compounds
Cao, Y., Jiang, T., & Girke, T. (2008) · Bioinformatics · doi:10.1093/bioinformatics/btn186 · Cited by 211 · see citing works
Do Structurally Similar Ligands Bind in a Similar Fashion?
Boström, J., Hogner, A., & Schmitt, S. (2006) · Journal of Medicinal Chemistry · doi:10.1021/jm060167o · Cited by 180 · see citing works
Graph theory and topology in chemistry
H.R., & Ot, W. (1988) · Journal of Molecular Structure THEOCHEM · doi:10.1016/0166-1280(88)80106-4 · Cited by 180 · see citing works
The Most Common Chemical Replacements in Drug-Like Compounds
Sheridan, R. P. (2002) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci0100806 · Cited by 167 · see citing works
Heuristics for Similarity Searching of Chemical Graphs Using a Maximum Common Edge Subgraph Algorithm
Raymond, J. W., Gardiner, E. J., & Willett, P. (2002) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci010381f · Cited by 151 · see citing works
Searching Techniques for Databases of Two- and Three-Dimensional Chemical Structures
Willett, P. (2005) · Journal of Medicinal Chemistry · doi:10.1021/jm0582165 · Cited by 151 · see citing works
Small Molecule Subgraph Detector (SMSD) toolkit
Rahman, S. A., Bashton, M., Holliday, G. L., Schrader, R., & Thornton, J. M. (2009) · Journal of Cheminformatics · doi:10.1186/1758-2946-1-12 · Cited by 127 · see citing works
Video indexing and similarity retrieval by largest common subgraph detection using decision trees
Shearer, K., Bunke, H., & Venkatesh, S. (2001) · Pattern Recognition · doi:10.1016/s0031-3203(00)00048-0 · Cited by 113 · see citing works
Common subgraph isomorphism detection by backtracking search
Krissinel, E., & Henrick, K. (2004) · Software Practice and Experience · doi:10.1002/spe.588 · Cited by 110 · see citing works
Maximum common subgraph isomorphism algorithms and their applications in molecular science: a review
Ehrlich, H., & Rarey, M. (2011) · Wiley Interdisciplinary Reviews Computational Molecular Science · doi:10.1002/wcms.5 · Cited by 101 · see citing works
Similarity methods in chemoinformatics
Willett, P. (2009) · Annual Review of Information Science and Technology · doi:10.1002/aris.2009.1440430108 · Cited by 99 · see citing works
Effectiveness of graph-based and fingerprint-based similarity measures for virtual screening of 2D chemical structure databases
Raymond, J. W., & Willett, P. (2002) · Journal of Computer-Aided Molecular Design · doi:10.1023/a:1016387816342 · Cited by 96 · see citing works
Chemoinformatics—an introduction for computer scientists
Brown, N. (2009) · ACM Computing Surveys · doi:10.1145/1459352.1459353 · Cited by 95 · see citing works
Simple ingredients leading to very efficient heuristics for the maximum clique problem
Grosso, A., Locatelli, M., & Pullan, W. (2007) · Journal of Heuristics · doi:10.1007/s10732-007-9055-x · Cited by 90 · see citing works
Scaffold Hopping Using Clique Detection Applied to Reduced Graphs
Barker, E. J., Buttar, D., Cosgrove, D. A., Gardiner, E. J., Kitts, P., Willett, P., & Gillet, V. J. (2006) · Journal of Chemical Information and Modeling · doi:10.1021/ci050347r · Cited by 89 · see citing works
Database Clustering with a Combination of Fingerprint and Maximum Common Substructure Methods
Ståhl, M., & Mauser, H. (2005) · Journal of Chemical Information and Modeling · doi:10.1021/ci050011h · Cited by 89 · see citing works
Use of a maximum common subgraph algorithm in the automatic identification of ostensible bond changes occurring in chemical reactions
McGregor, J. J., & Willett, P. (1981) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci00031a005 · Cited by 81 · see citing works
Build-Up Algorithm for Atomic Correspondence between Chemical Structures
Kawabata, T. (2011) · Journal of Chemical Information and Modeling · doi:10.1021/ci2001023 · Cited by 75 · see citing works
Automatic identification of molecular similarity using reduced-graph representation of chemical structure
Takahashi, Y., Sukekawa, M., & Sasaki, S. (1992) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci00010a009 · Cited by 72 · see citing works
fmcsR: mismatch tolerant maximum common substructure searching in R
Wang, Y., Backman, T. W. H., Horan, K., & Girke, T. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt475 · Cited by 62 · see citing works
Kinase Patent Space Visualization Using Chemical Replacements
Southall, N. T., & Ajay (2006) · Journal of Medicinal Chemistry · doi:10.1021/jm051201m · Cited by 54 · see citing works
A Robust Clustering Method for Chemical Structures
Ståhl, M., Mauser, H., Tsui, M., & Taylor, N. R. (2005) · Journal of Medicinal Chemistry · doi:10.1021/jm040213p · Cited by 52 · see citing works
3D Flexible Alignment Using 2D Maximum Common Substructure: Dependence of Prediction Accuracy on Target-Reference Chemical Similarity
Kawabata, T., & Nakamura, H. (2014) · Journal of Chemical Information and Modeling · doi:10.1021/ci500006d · Cited by 52 · see citing works
FMCS: a novel algorithm for the multiple MCS problem
Dalke, A., & Hastings, J. (2013) · Journal of Cheminformatics · doi:10.1186/1758-2946-5-s1-o6 · Cited by 52 · see citing works
Nonlinear Scoring Functions for Similarity-Based Ligand Docking and Binding Affinity Prediction
Bryliński, M. (2013) · Journal of Chemical Information and Modeling · doi:10.1021/ci400510e · Cited by 50 · see citing works
MultiMCS: A Fast Algorithm for the Maximum Common Substructure Problem on Multiple Molecules
Hariharan, R., Janakiraman, A., Nilakantan, R., Singh, B., Varghese, S., Landrum, G. A., & Schuffenhauer, A. (2011) · Journal of Chemical Information and Modeling · doi:10.1021/ci100297y · Cited by 47 · see citing works
Graph-Based Molecular Alignment (GMA)
Marialke, J., Körner, R., Tietze, S., & Apostolakis, J. (2007) · Journal of Chemical Information and Modeling · doi:10.1021/ci600387r · Cited by 45 · see citing works
ReactionMap: An Efficient Atom-Mapping Algorithm for Chemical Reactions
Fooshee, D. R., Andronico, A., & Baldi, P. (2013) · Journal of Chemical Information and Modeling · doi:10.1021/ci400326p · Cited by 43 · see citing works
Matching two-dimensional chemical graphs using genetic algorithms
Brown, R. D., Jones, G., Willett, P., & Glen, R. C. (1994) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci00017a008 · Cited by 43 · see citing works
Representing Clusters Using a Maximum Common Edge Substructure Algorithm Applied to Reduced Graphs and Molecular Graphs
Gardiner, E. J., Gillet, V. J., Willett, P., & Cosgrove, D. A. (2007) · Journal of Chemical Information and Modeling · doi:10.1021/ci600444g · Cited by 42 · see citing works
Rationalizing Lead Optimization by Associating Quantitative Relevance with Molecular Structure Modification
Raymond, J. W., Watson, I. A., & Mahoui, A. (2009) · Journal of Chemical Information and Modeling · doi:10.1021/ci9000426 · Cited by 38 · see citing works
Toward an Improved Clustering of Large Data Sets Using Maximum Common Substructures and Topological Fingerprints
Böcker, A. (2008) · Journal of Chemical Information and Modeling · doi:10.1021/ci8000887 · Cited by 37 · see citing works
MCSS: a new algorithm for perception of maximal common substructures and its application to NMR spectral studies. 1. The algorithm
Chen, L., & Robien, W. (1992) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci00009a016 · Cited by 25 · see citing works
EMCSS: A New Method for Maximal Common Substructure Search
Wang, T., & Zhou, J. (1997) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci9601675 · Cited by 20 · see citing works
Integration of Ligand-Based Drug Screening with Structure-Based Drug Screening by Combining Maximum Volume Overlapping Score with Ligand Docking
Fukunishi, Y., & Nakamura, H. (2012) · Pharmaceuticals · doi:10.3390/ph5121332 · Cited by 12 · see citing works

Flagged first, then by citations

1 of the 56 references couldn’t be matched to a known paper.

Sorted by citations

QSAR without borders
Muratov, E. N., Bajorath, J., Sheridan, R. P., Tetko, I. V., Filimonov, D., Poroikov, V., Oprea, T. I., Baskin, I. I., Varnek, A., Roitberg, A., et al. (2020) · Chemical Society Reviews · doi:10.1039/d0cs00098a · Cited by 913 · see citing works
Root-aligned SMILES: a tight representation for chemical reaction prediction
Zhong, Z., Song, J., Feng, Z., Liu, T., Jia, L., Yao, S., Wu, M., Hou, T., & Song, M. (2022) · Chemical Science · doi:10.1039/d2sc02763a · Cited by 91 · see citing works
Coverage bias in small molecule machine learning
Kretschmer, F., Seipp, J., Ludwig, M., Klau, G. W., & Böcker, S. (2025) · Nature Communications · doi:10.1038/s41467-024-55462-w · Cited by 76 · see citing works
Maximum Common Substructure Searching in Combinatorial Make-on-Demand Compound Spaces
Schmidt, R., Klein, R., & Rarey, M. (2021) · Journal of Chemical Information and Modeling · doi:10.1021/acs.jcim.1c00640 · Cited by 61 · see citing works
When Does Chemical Elaboration Induce a Ligand To Change Its Binding Mode?
Malhotra, S., & Karanicolas, J. (2016) · Journal of Medicinal Chemistry · doi:10.1021/acs.jmedchem.6b00725 · Cited by 59 · see citing works
A novel molecular class that recruits HDAC/MECP2 complexes to PU.1 motifs reduces neuroinflammation
Ralvenius, W. T., Mungenast, A. E., Woolf, H., Huston, M. M., Gillingham, T. Z., Godin, S. K., Penney, J., Cam, H. P., Gao, F., Fernandez, C. G., et al. (2023) · Journal of Experimental Medicine · doi:10.1084/jem.20222105 · Cited by 31 · see citing works
“Structure – activity relationship analysis was performed using maximum common substructure analysis with the Pipeline Pilot (Dassault Systèmes) software (Englert and Kov´acs, 2015).”
Rubiscolins are naturally occurring G protein-biased delta opioid receptor peptides
Cassell, R. J., Mores, K. L., Zerfas, B. L., Mahmoud, A. H., Lill, M. A., Trader, D. J., & van Rijn, R. M. (2018) · European Neuropsychopharmacology · doi:10.1016/j.euroneuro.2018.12.013 · Cited by 30 · see citing works
Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems
McCreesh, C., Ndiaye, S., Prosser, P., & Solnon, C. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-44953-1_23 · Cited by 29 · see citing works
Analysis of drug–endogenous human metabolite similarities in terms of their maximum common substructures
O’Hagan, S., & Kell, D. B. (2017) · Journal of Cheminformatics · doi:10.1186/s13321-017-0198-y · Cited by 26 · see citing works
Spectrophores as one-dimensional descriptors calculated from three-dimensional atomic properties: applications ranging from scaffold hopping to multi-target virtual screening
Gladysz, R., dos Santos, F. M., Langenaeker, W., Thijs, G., Augustyns, K., & Winter, H. L. D. (2018) · Journal of Cheminformatics · doi:10.1186/s13321-018-0268-9 · Cited by 24 · see citing works
The Maximum Common Subgraph Problem: A Parallel and Multi-Engine Approach
Quer, S., Marcelli, A., & Squillero, G. (2020) · Computation · doi:10.3390/computation8020048 · Cited by 21 · see citing works
Comparison of Maximum Common Subgraph Isomorphism Algorithms for the Alignment of 2D Chemical Structures
Duesbury, E., Holliday, J. D., & Willett, P. (2017) · ChemMedChem · doi:10.1002/cmdc.201700482 · Cited by 18 · see citing works
An Integrative in silico Drug Repurposing Approach for Identification of Potential Inhibitors of SARS‐CoV‐2 Main Protease
Djoković, N., Ružić, D., Djikić, T., Cvijić, S., Ignjatović, J., Ibric, S. R., Baralić, K., Djordjević, A. B., Ćurčić, M., Đukić-Ćosić, D., et al. (2021) · Molecular Informatics · doi:10.1002/minf.202000187 · Cited by 12 · see citing works
A Strengthened Branch and Bound Algorithm for the Maximum Common (Connected) Subgraph Problem
Zhou, J., He, K., Zheng, J., Li, C.-M., & Liu, Y. (2022) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2022/265 · Cited by 11 · see citing works
Enumerating common molecular substructuresPreprint
Engler, M. S., El-Kebir, M., Mulder, J., Mark, A. E., Geerke, D. P., & Klau, G. W. (2017) · doi:10.7287/peerj.preprints.3250v1 · Cited by 11 · see citing works
Hybrid Learning with New Value Function for the Maximum Common Induced Subgraph Problem
Liu, Y., Zhao, J., Li, C.-M., Jiang, H., & He, K. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i4.25519 · Cited by 10 · see citing works
Disconnected Maximum Common Substructures under Constraints
Schmidt, R., Krull, F., Heinzke, A. L., & Rarey, M. (2020) · Journal of Chemical Information and Modeling · doi:10.1021/acs.jcim.0c00741 · Cited by 10 · see citing works
The Multi-Maximum and Quasi-Maximum Common Subgraph Problem
Cardone, L., & Quer, S. (2023) · Computation · doi:10.3390/computation11040069 · Cited by 8 · see citing works
Computational Method for Structure-Based Analysis of SAR Transfer
Bonanni, D., Lolli, M. L., & Bajorath, J. (2020) · Journal of Medicinal Chemistry · doi:10.1021/acs.jmedchem.9b01931 · Cited by 7 · see citing works
Chemical Similarity and Substructure Searches
Koch, O., Kriege, N. M., & Humbeck, L. (2018) · Elsevier eBooks · doi:10.1016/b978-0-12-809633-8.20195-7 · Cited by 6 · see citing works
Automatic generation of Markush structures from specific compounds
Kovács, P., Botka, G., & Figyelmesi, Á. (2019) · World Patent Information · doi:10.1016/j.wpi.2019.03.006 · Cited by 5 · see citing works
Self-citation
The Maximum Common Substructure (MCS) Search as a New Tool for SAR and QSAR
Golbamaki, A., Franchi, A. M., & Gini, G. C. (2017) · Challenges and advances in computational chemistry and physics · doi:10.1007/978-3-319-56850-8_5 · Cited by 3 · see citing works
Guided Iterative Substructure Search (GI-SSS) - A New Trick for an Old Dog
Weskamp, N. (2016) · Molecular Informatics · doi:10.1002/minf.201600063 · Cited by 1 · see citing works
Identification of metabolites identical and similar to drugs as candidates for metabolic engineering
Sinatti, V. V. C., Gonçalves, C. A. X., & Romão‐Dumaresq, A. S. (2019) · Journal of Biotechnology · doi:10.1016/j.jbiotec.2019.06.303 · Cited by 1 · see citing works
Eﬃcient Algorithms for Graph Optimization Problems
Kovács, P. (2019) · Eötvös Loránd Tudományegyetem · doi:10.15476/elte.2019.029 · Cited by 1 · see citing works
Self-citation
Molecular LEGION: incalculably large coverage of chemical space around the NLRP3 target
Zagribelnyy, B. A., Aladinskiy, V., Bondarev, N., Ilin, I. S., Malkov, M., Vasileva, A. A., Ding, X., Lin, A., Shayakhmetov, R., Aliper, A., et al. (2026) · Scientific Data · doi:10.1038/s41597-026-06850-y · Cited by 1 · see citing works
SAR/QSAR
Teijeira, M., & Celeiro, M. (2018) · Springer eBooks · doi:10.1007/978-3-319-93233-0_21
Chemical Similarity and Substructure Searches
Kriege, N. M., Seidel, T., Humbeck, L., & Lessel, U. F. (2024) · Elsevier eBooks · doi:10.1016/b978-0-323-95502-7.00048-8
Common Substructures Extraction in Compounds: A Heuristic using Fragment Segmentation and Chemical Structure Notation
Narita, K., Du, W., Zhao, L., & Han, L. (2024) · IEEE/ACIS International Conference on Big Data, Cloud Computing, and Data Science (BCD) · doi:10.1109/bcd61269.2024.10743092
Correlation-Aware Secure Sorting and Permutation for Iterative Two-Party Graph Analysis
Chen, Y., Yu, J., Chen, K., Fan, X., Zhu, X., & Chen, W. (2025) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3719027.3765050
Machine Learning-Guided Discovery of Bacterial-Selective Membrane-Active Compounds Reveals Mechanistic Bias in Antibiotic Training DatasetsPreprint
Chain, C., Ghaffari, S., Belakaria, S., Sheehan, J. P., Irani, I., Wu, C.-Y., Kim, H., Engelhardt, B. E., & Gitai, Z. (2026) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.64898/2026.06.08.730938
A Comprehensive 19 F NMR Framework for Fragment‐Based Drug Discovery: The Validated Screening Library OpenFL600 and Efficient Affinity Ranking by CSAR
Rüdisser, S., Stadler, G. R., Padroni, G., Barbash, D., Ruckstuhl, M., Lorz, N., Jordan, C., Skibinski, S., Stühlinger, T. T., Kratzwald, S. E., et al. (2026) · Angewandte Chemie · doi:10.1002/ange.9964915
A Comprehensive 19 F NMR Framework for Fragment‐Based Drug Discovery: The Validated Screening Library OpenFL600 and Efficient Affinity Ranking by CSAR
Rüdisser, S., Stadler, G. R., Padroni, G., Barbash, D., Ruckstuhl, M., Lorz, N., Jordan, C., Skibinski, S., Stühlinger, T. T., Kratzwald, S. E., et al. (2026) · Angewandte Chemie International Edition · doi:10.1002/anie.9964915
Virtual Screening, Molecular Dynamics, and Density Functional Theory Identify Piperolein A as a Putative Dual PPARα/γ Modulator Relevant to Radiation‐Induced Cognitive Decline
Raj, J. A. T., Shinde, I., Chatterjee, A., Ghanekar, S., Gadewal, N. S., Chandrani, P., & Goda, J. S. (2026) · ChemistrySelect · doi:10.1002/slct.74090
Exact Enumeration of All Connected Maximum
Petersen, J. B. S., Davoodi, A., Gärtner, T., Hellmuth, M., & Merkle, D. (2026) · match Communications in Mathematical and in Computer Chemistry · doi:10.46793/match.97-2.12126
Candidate Structure Prioritization in Non-Target Screening with Predicted Collision Cross-Sections and Uncertainty Quantification
Plo, L. F., & Kruve, A. (2026) · Journal of Chemical Information and Modeling · doi:10.1021/acs.jcim.6c02492
BindingDB Entry 50047982: When Does Chemical Elaboration Induce a Ligand To Change Its Binding Mode?
BindingDB (2018) · UC San Diego · doi:10.7270/q2rx9f10

Making the most of approximate maximum common substructure search
Englert, P. A. J., & Kovács, P. (2014) · Journal of Cheminformatics · doi:10.1186/1758-2946-6-s1-p29 · Cited by 1 · see citing works
Self-citation
Comparison of Maximum Common Subgraph Isomorphism Algorithms for the Alignment of 2D Chemical Structures
Duesbury, E., Holliday, J. D., & Willett, P. (2017) · ChemMedChem · doi:10.1002/cmdc.201700482 · Cited by 18 · see citing works
Step-by-Step Calculation of All Maximum Common Substructures through a Constraint Satisfaction Based Algorithm
García, G. C., Ruiz, I. L., & Gómez‐Nieto, M. Á. (2003) · Journal of Chemical Information and Computer Sciences · doi:10.1021/ci034167y · Cited by 25 · see citing works
POSTER PRESENTATION Open Access Making the most of approximate maximum
Englert, P., & Kovács, P. (2016)
Self-citation
Chemical Similarity and Substructure Searches
Koch, O., Kriege, N. M., & Humbeck, L. (2018) · Elsevier eBooks · doi:10.1016/b978-0-12-809633-8.20195-7 · Cited by 6 · see citing works

Authors: Englert, P., & Kovács, P.
Affiliations: Department of Algorithms and Applications, Eötvös Loránd University, Budapest 1117, Hungary
ChemAxon Ltd., Budapest 1031, Hungary
Corresponding author: Kovács, Péter
ORCID: Kovács, Péter
Venue: Journal of Chemical Information and Modeling
Publisher: American Chemical Society (ACS)
Published: 2015-05-01
Volume: 55
Issue: 5
Pages: 941-955
ISSN: 1549-9596 (ISSN-L)
1549-960X
DOI: 10.1021/acs.jcim.5b00036
OpenAlex: W2001431291
Cited by: 36
References: 56
Citations by year: 2026: 7 · 2025: 2 · 2024: 2 · 2023: 3 · 2022: 2 · 2021: 2 · 2020: 4 · 2019: 3 · 2018: 4 · 2017: 4 · 2016: 3
FWCI: 4.11
Type: journal article
Language: en
Open access: closed
Locations: Journal of Chemical Information and Modeling (publishedVersion)
PubMed (publishedVersion)
Topics: Physical Sciences › Computer Science › Computational Theory and Mathematics › Computational Drug Discovery Methods
Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
Keywords: maximum common substructure, heuristic algorithms, atom mapping, cheminformatics, molecular similarity search, lead optimization, indigo
MeSH terms: Computer Heuristics, Time Factors, Drug Discovery

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Efficient Heuristics for Maximum Common Substructure Search

Abstract

Integrity signals

Claims the paper makes

Cites

Cited by

Related

Record

About these checks