Skip to main content
Top

2017 | OriginalPaper | Chapter

The Maximum Common Substructure (MCS) Search as a New Tool for SAR and QSAR

Authors : Azadi Golbamaki, Alessio Mauro Franchi, Giuseppina Gini

Published in: Advances in QSAR Modeling

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The Maximum Common Substructure (MCS) between two molecules induces a similarity that makes it possible to group compounds sharing the same pattern. In our study the relevance of a similarity measure exclusively based on MCS has been implemented in new software based on the fmcs_R package. The newly developed program searches for the largest substructures between a target molecule, with unknown property value, and a set of similar molecules with experimental value to assess the toxicity of the target chemical. In QSAR and read-across, while reasoning on the similarity of the evaluated molecules, another important aspect to consider is the difference of two molecules that share a large common part. Thus, the present study examines the issue of the MCS itself, and the differences between a reference and a similar molecule by the aid of an ad hoc developed software. The most important features of this software are: (I) the process of the MCSs between two molecules represented as graphs and (II) the detection and the graphical representation of the dissimilar substructures that are identified in the target and the source molecules. The user may consequently quantify the properties and weights of these substructures to improve the assessment of new substances. This new software is integrated into ToxRead, a system to visualize structures and substructures for expert reasoning. Moreover, an automatic search in a database containing the role of small substructures in amplifying or reducing the property can help in improving the final assessment.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
go back to reference Bron, C., & Kerbosch, J. (1973). Finding all the cliques in an undirected graph. Communication of the Association for Computing Machinery (ACM), 16(9), 189–201. Bron, C., & Kerbosch, J. (1973). Finding all the cliques in an undirected graph. Communication of the Association for Computing Machinery (ACM), 16(9), 189–201.
go back to reference Bunke, H., & Messmer, B. T. (1995). Efficient attributed graph matching and its application to image analysis. In Proceeding of Image Analysis and Processing (pp. 45–55). doi:10.1007/3-540-60298-4_235. Bunke, H., & Messmer, B. T. (1995). Efficient attributed graph matching and its application to image analysis. In Proceeding of Image Analysis and Processing (pp. 45–55). doi:10.​1007/​3-540-60298-4_​235.
go back to reference Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2004). A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10), 1367–1372.CrossRef Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (2004). A (sub)graph isomorphism algorithm for matching large graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(10), 1367–1372.CrossRef
go back to reference Cuissart, B., Touffet, F., Cremilleux, B., Bureau, R., & Rault, S. (2002). The maximum common substructure as a molecular depiction in a supervised classification context: Experiments in quantitative structure/biodegradability relationships. Journal of Chemical Information and Modelling, 42(5), 1043–1052. doi:10.1021/ci020017w. Cuissart, B., Touffet, F., Cremilleux, B., Bureau, R., & Rault, S. (2002). The maximum common substructure as a molecular depiction in a supervised classification context: Experiments in quantitative structure/biodegradability relationships. Journal of Chemical Information and Modelling, 42(5), 1043–1052. doi:10.​1021/​ci020017w.
go back to reference Duesbury, E., Holliday, J., & Willett, P. (2015). Maximum common substructure-based data fusion in similarity searching. Journal of Chemical Information and Modelling, 55(2), 222–230.CrossRef Duesbury, E., Holliday, J., & Willett, P. (2015). Maximum common substructure-based data fusion in similarity searching. Journal of Chemical Information and Modelling, 55(2), 222–230.CrossRef
go back to reference Englert, P., & Kovacs, P. (2015). Efficient heuristics for maximum common substructure search. Journal of Chemical Information and Modelling, 55(5), 941–955.CrossRef Englert, P., & Kovacs, P. (2015). Efficient heuristics for maximum common substructure search. Journal of Chemical Information and Modelling, 55(5), 941–955.CrossRef
go back to reference Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. : W.H. Freeman. ISBN 0-7167-1045-5. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. : W.H. Freeman. ISBN 0-7167-1045-5.
go back to reference Gini, G., Ferrari, T., Cattaneo, D., Golbamaki, N., Manganaro, A., & Benfenati, E. (2013). Automatic knowledge extraction from chemical structures: The case of mutagenicity prediction. SAR and QSAR in Environmental Research, 24(5), 365–383.CrossRef Gini, G., Ferrari, T., Cattaneo, D., Golbamaki, N., Manganaro, A., & Benfenati, E. (2013). Automatic knowledge extraction from chemical structures: The case of mutagenicity prediction. SAR and QSAR in Environmental Research, 24(5), 365–383.CrossRef
go back to reference Gini, G., Franchi, A. M., Manganaro, A., Golbamaki, A., & Benfenati, E. (2014). ToxRead: A tool to assist in read across and its use to assess mutagenicity of chemicals. SAR and QSAR in Environmental Research, 25(12), 999–1011.CrossRef Gini, G., Franchi, A. M., Manganaro, A., Golbamaki, A., & Benfenati, E. (2014). ToxRead: A tool to assist in read across and its use to assess mutagenicity of chemicals. SAR and QSAR in Environmental Research, 25(12), 999–1011.CrossRef
go back to reference Gini, G., Lorenzini, M., Benfenati, E., Brambilla, R., & Malvè, L. (2001). Mixing a symbolic and a subsymbolic expert to improve carcinogenicity prediction of aromatic compounds. In Proceedings of the Second International Workshop on Multiple Classifier Systems (MCS 2001), July 2001 (pp. 126–135). Cambridge (UK): Springer. Gini, G., Lorenzini, M., Benfenati, E., Brambilla, R., & Malvè, L. (2001). Mixing a symbolic and a subsymbolic expert to improve carcinogenicity prediction of aromatic compounds. In Proceedings of the Second International Workshop on Multiple Classifier Systems (MCS 2001), July 2001 (pp. 126–135). Cambridge (UK): Springer.
go back to reference Hansch, C., & Leo, A. (1979). Substituent constants for correlation analysis in chemistry and biology. New York: Wiley. Hansch, C., & Leo, A. (1979). Substituent constants for correlation analysis in chemistry and biology. New York: Wiley.
go back to reference Kuhl, F. S., Crippen, G. M., & Friesen, D. K. (1983). A combinatorial algorithm for calculating ligand binding. Journal of Computational Chemistry, 5(1), 24–34.CrossRef Kuhl, F. S., Crippen, G. M., & Friesen, D. K. (1983). A combinatorial algorithm for calculating ligand binding. Journal of Computational Chemistry, 5(1), 24–34.CrossRef
go back to reference Reymond, J.-L., & Awale, M. (2012). Exploring chemical space for drug discovery using the chemical universe database. ACS Chemical Neuroscience, 3(9), 649–657. doi:10.1021/cn3000422, PMID: 23019491. Reymond, J.-L., & Awale, M. (2012). Exploring chemical space for drug discovery using the chemical universe database. ACS Chemical Neuroscience, 3(9), 649–657. doi:10.​1021/​cn3000422, PMID: 23019491.
go back to reference Raymod, J. W., Gardiner, E. J., & Willet, P. (2002). RASCAL: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal, 45(6), 631–644.CrossRef Raymod, J. W., Gardiner, E. J., & Willet, P. (2002). RASCAL: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal, 45(6), 631–644.CrossRef
go back to reference Raymond, J. W., & Willett, P. (2002). Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of Computer-Aided Molecular Design, 16(7), 521–533.CrossRef Raymond, J. W., & Willett, P. (2002). Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of Computer-Aided Molecular Design, 16(7), 521–533.CrossRef
go back to reference Rhodes, N., Willett, P., Calvet, A., Dunbar, J. B., & Humblet, C. (2003). CLIP: Similarity searching of 3D databases using clique detection. Journal of Chemical Information and Computer Science, 43(2), 443–448.CrossRef Rhodes, N., Willett, P., Calvet, A., Dunbar, J. B., & Humblet, C. (2003). CLIP: Similarity searching of 3D databases using clique detection. Journal of Chemical Information and Computer Science, 43(2), 443–448.CrossRef
go back to reference Stah, M., Mauser, H., & Hoffmann, F. (2005). Database clustering with a combination of fingerprint and maximum common substructure methods. Journal of Chemical Information and Computer Science., 45(3), 542–548.CrossRef Stah, M., Mauser, H., & Hoffmann, F. (2005). Database clustering with a combination of fingerprint and maximum common substructure methods. Journal of Chemical Information and Computer Science., 45(3), 542–548.CrossRef
go back to reference Tanimoto, T. (1958). An elementary mathematical theory of classification and prediction. Internal IBM Technical Report. Tanimoto, T. (1958). An elementary mathematical theory of classification and prediction. Internal IBM Technical Report.
go back to reference Toropov, A. P., Toropov, A. A., Lombardo, A., Roncaglioni, A., Benfenati, E., & Gini, G. (2010). A new bioconcentration factor model based on SMILES and indices of presence of atoms. European Journal of Medicinal Chemistry, 45(9), 4399–4402.CrossRef Toropov, A. P., Toropov, A. A., Lombardo, A., Roncaglioni, A., Benfenati, E., & Gini, G. (2010). A new bioconcentration factor model based on SMILES and indices of presence of atoms. European Journal of Medicinal Chemistry, 45(9), 4399–4402.CrossRef
go back to reference Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. Journal of the ACM, 23(1), 31–42.CrossRef Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. Journal of the ACM, 23(1), 31–42.CrossRef
go back to reference Xu, J. (1996). GMA: A generic match algorithm for structural homomorphism, isomorphism, and maximal common substructure match and its applications. Journal of Chemical Information and Computer Science., 36(1), 25–34.CrossRef Xu, J. (1996). GMA: A generic match algorithm for structural homomorphism, isomorphism, and maximal common substructure match and its applications. Journal of Chemical Information and Computer Science., 36(1), 25–34.CrossRef
go back to reference Zhu, Y., Oin, L., & Yu, J. X. (2013). High efficiency and quality: Large graphs matching. The International Journal on Very Large Data Bases, 22(3), 345–368.CrossRef Zhu, Y., Oin, L., & Yu, J. X. (2013). High efficiency and quality: Large graphs matching. The International Journal on Very Large Data Bases, 22(3), 345–368.CrossRef
Metadata
Title
The Maximum Common Substructure (MCS) Search as a New Tool for SAR and QSAR
Authors
Azadi Golbamaki
Alessio Mauro Franchi
Giuseppina Gini
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-56850-8_5

Premium Partner