{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T16:33:09Z","timestamp":1740155589247,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,12,1]],"date-time":"2020-12-01T00:00:00Z","timestamp":1606780800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T00:00:00Z","timestamp":1608163200000},"content-version":"vor","delay-in-days":16,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Projekt DEAL"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cheminform"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An important task in cheminformatics is to test whether two molecules are equivalent with respect to their 2D structure. Mathematically, this amounts to solving the graph isomorphism problem for labelled graphs. In this paper, we present an approach which exploits chemical properties and the local neighbourhood of atoms to define highly distinctive node labels. These characteristic labels are the key for clever partitioning molecules into molecule equivalence classes and an effective equivalence test. Based on extensive computational experiments, we show that our algorithm is significantly faster than existing implementations within ,  and . We provide our Java implementation as an easy-to-use, open-source package (via GitHub) which is compatible with . It fully supports the distinction of different isotopes and molecules with radicals.<\/jats:p>","DOI":"10.1186\/s13321-020-00480-1","type":"journal-article","created":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T09:07:17Z","timestamp":1608196037000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["MET: a Java package for fast molecule equivalence testing"],"prefix":"10.1186","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2594-7909","authenticated-orcid":false,"given":"J\u00f6rdis-Ann","family":"Sch\u00fcler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3445-8645","authenticated-orcid":false,"given":"Steffen","family":"Rechner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6976-0006","authenticated-orcid":false,"given":"Matthias","family":"M\u00fcller-Hannemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,12,17]]},"reference":[{"key":"480_CR1","volume-title":"Computers and intractability: a guide to the theorey of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theorey of NP-completeness. W.H. Freeman & Co, New York"},{"issue":"3","key":"480_CR2","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1021\/ci9702914","volume":"38","author":"J-L Faulon","year":"1998","unstructured":"Faulon J-L (1998) Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs. J Chem Inf Comput Sci 38(3):432\u2013444. https:\/\/doi.org\/10.1021\/ci9702914","journal-title":"J Chem Inf Comput Sci"},{"key":"480_CR3","doi-asserted-by":"publisher","unstructured":"Babai L (2016) Graph isomorphism in quasipolynomial time [extended abstract]. In: Proceedings of the forty-eighth annual ACM symposium on theory of computing. STOC \u201916. Association for Computing Machinery, New York, NY, USA, pp 684\u2013697. https:\/\/doi.org\/10.1145\/2897518.2897542","DOI":"10.1145\/2897518.2897542"},{"key":"480_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/j.dam.2018.02.018","volume":"242","author":"A J\u00fcttner","year":"2018","unstructured":"J\u00fcttner A, Madarasi P (2018) Vf2++\u2014an improved subgraph isomorphism algorithm. Computational advances in combinatorial optimization. Discret Appl Math 242:69\u201381. https:\/\/doi.org\/10.1016\/j.dam.2018.02.018","journal-title":"Discret Appl Math"},{"key":"480_CR5","doi-asserted-by":"publisher","DOI":"10.1201\/9781420082999","volume-title":"Handbook of chemoinformatics algorithms","author":"J-L Faulon","year":"2010","unstructured":"Faulon J-L, Bender A (2010) Handbook of chemoinformatics algorithms. Taylor and Francis Group, London"},{"key":"480_CR6","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0022-0000(82)90009-5","volume":"25","author":"EM Luks","year":"1982","unstructured":"Luks EM (1982) Isomorphism of graphs of bounded valence can be tested in polynomial time. J Comput Syst Sci 25:42\u201365","journal-title":"J Comput Syst Sci"},{"issue":"1","key":"480_CR7","first-page":"254","volume":"1","author":"CS Chowdary","year":"2009","unstructured":"Chowdary CS, Mitra P (2009) Novel method for improving the exact matching of the molecular graphs. Int J Recent Trends Eng 1(1):254\u2013259","journal-title":"Int J Recent Trends Eng"},{"key":"480_CR8","first-page":"45","volume":"30","author":"BD McKay","year":"1981","unstructured":"McKay BD (1981) Practical graph isomorphism. Congr Numer 30:45\u201387","journal-title":"Congr Numer"},{"issue":"1","key":"480_CR9","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann JR (1976) An algorithm for subgraph isomorphism. J ACM 23(1):31\u201342. https:\/\/doi.org\/10.1145\/321921.321925","journal-title":"J ACM"},{"key":"480_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1671970.1921702","volume":"15","author":"JR Ullmann","year":"2011","unstructured":"Ullmann JR (2011) Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism. J Exp Algorithmics 15:1\u201361116164. https:\/\/doi.org\/10.1145\/1671970.1921702","journal-title":"J Exp Algorithmics"},{"key":"480_CR11","doi-asserted-by":"crossref","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (1999) Performance evaluation of the vf graph matching algorithm. In: Proceedings of the 10th international conference on image analysis and processing. ICIAP \u201999. IEEE Computer Society, USA, p 1172","DOI":"10.1109\/ICIAP.1999.797762"},{"issue":"10","key":"480_CR12","doi-asserted-by":"publisher","first-page":"1367","DOI":"10.1109\/TPAMI.2004.75","volume":"26","author":"LP Cordella","year":"2004","unstructured":"Cordella LP, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans Pattern Anal Mach Intell 26(10):1367\u20131372. https:\/\/doi.org\/10.1109\/TPAMI.2004.75","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"480_CR13","doi-asserted-by":"publisher","unstructured":"Carletti V, Foggia P, Vento M (2015) VF2 Plus: an improved version of VF2 for biological graphs. In: Graph-based representations in pattern recognition. Springer, Switzerland, pp 168\u2013177. https:\/\/doi.org\/10.1007\/978-3-319-18224-7_17","DOI":"10.1007\/978-3-319-18224-7_17"},{"key":"480_CR14","unstructured":"Landrum G (2020) The RDKit Documentation. http:\/\/www.rdkit.org\/docs\/RDKit_Book.html. Accessed 03 Nov 2020"},{"issue":"1","key":"480_CR15","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1186\/s13321-017-0220-4","volume":"9","author":"EL Willighagen","year":"2017","unstructured":"Willighagen EL, Mayfield JW, Alvarsson J, Berg A, Carlsson L, Jeliazkova N, Kuhn S, Pluskal T, Rojas-Chert\u00f3 M, Spjuth O, Torrance G, Evelo CT, Guha R, Steinbeck C (2017) The chemistry development kit (cdk) v2.0: atom typing, depiction, molecular formulas, and substructure searching. J Cheminform 9(1):33. https:\/\/doi.org\/10.1186\/s13321-017-0220-4","journal-title":"J Cheminform"},{"issue":"1","key":"480_CR16","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1186\/1758-2946-1-12","volume":"1","author":"SA Rahman","year":"2009","unstructured":"Rahman SA, Bashton M, Holliday GL, Schrader R, Thornton JM (2009) Small molecule subgraph detector (SMSD) toolkit. J Cheminform 1(1):12. https:\/\/doi.org\/10.1186\/1758-2946-1-12","journal-title":"J Cheminform"},{"issue":"1","key":"480_CR17","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1021\/ci00057a005","volume":"28","author":"D Weininger","year":"1988","unstructured":"Weininger D (1988) Smiles, a chemical language and information system. 1. Introduction to methodology and encoding rules. J Chem Inf Comput Sci 28(1):31\u201336. https:\/\/doi.org\/10.1021\/ci00057a005","journal-title":"J Chem Inf Comput Sci"},{"issue":"2","key":"480_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1021\/ci00062a008","volume":"29","author":"D Weininger","year":"1989","unstructured":"Weininger D, Weininger A, Weininger JL (1989) Smiles. 2. Algorithm for generation of unique smiles notation. J Chem Inf Comput Sci 29(2):97\u2013101. https:\/\/doi.org\/10.1021\/ci00062a008","journal-title":"J Chem Inf Comput Sci"},{"issue":"1","key":"480_CR19","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1186\/1758-2946-5-7","volume":"5","author":"S Heller","year":"2013","unstructured":"Heller S, McNaught A, Stein S, Tchekhovskoi D, Pletnev I (2013) Inchi\u2014the worldwide chemical structure identifier standard. J Cheminform 5(1):7. https:\/\/doi.org\/10.1186\/1758-2946-5-7","journal-title":"J Cheminform"},{"issue":"1","key":"480_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1186\/s13321-015-0068-4","volume":"7","author":"SR Heller","year":"2015","unstructured":"Heller SR, McNaught A, Pletnev I, Stein S, Tchekhovskoi D (2015) Inchi, the iupac international chemical identifier. J Cheminform 7(1):23. https:\/\/doi.org\/10.1186\/s13321-015-0068-4","journal-title":"J Cheminform"},{"issue":"10","key":"480_CR21","doi-asserted-by":"publisher","first-page":"2111","DOI":"10.1021\/acs.jcim.5b00543","volume":"55","author":"N Schneider","year":"2015","unstructured":"Schneider N, Sayle RA, Landrum GA (2015) Get your atoms in order\u2014an open-source implementation of a novel and robust molecular canonicalization algorithm. J Chem Inf Model 55(10):2111\u20132120. https:\/\/doi.org\/10.1021\/acs.jcim.5b00543 PMID: 26441310","journal-title":"J Chem Inf Model"},{"issue":"1","key":"480_CR22","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1186\/1758-2946-4-22","volume":"4","author":"NM O\u2019Boyle","year":"2012","unstructured":"O\u2019Boyle NM (2012) Towards a universal smiles representation\u2014a standard method to generate canonical smiles based on the inchi. J Cheminform 4(1):22. https:\/\/doi.org\/10.1186\/1758-2946-4-22","journal-title":"J Cheminform"},{"issue":"5","key":"480_CR23","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1186\/1758-2946-4-22","volume":"264","author":"B Dezs\u0151","year":"2011","unstructured":"Dezs\u0151 B, J\u00fcttner A, Kov\u00e1cs P (2011) Lemon\u2014an open source c++ graph template library. Electron Notes Theor Comput Sci 264(5):23\u201345. https:\/\/doi.org\/10.1016\/j.entcs.2011.06.003","journal-title":"Electron Notes Theor Comput Sci"},{"issue":"1","key":"480_CR24","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1186\/s13321-016-0148-0","volume":"8","author":"NM O\u2019Boyle","year":"2016","unstructured":"O\u2019Boyle NM, Sayle RA (2016) Comparing structural fingerprints using a literature-based similarity benchmark. J Cheminform 8(1):36. https:\/\/doi.org\/10.1186\/s13321-016-0148-0","journal-title":"J Cheminform"},{"issue":"1","key":"480_CR25","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1186\/s13321-018-0321-8","volume":"10","author":"D Probst","year":"2018","unstructured":"Probst D, Reymond J-L (2018) A probabilistic molecular fingerprint for big data settings. J Cheminform 10(1):66. https:\/\/doi.org\/10.1186\/s13321-018-0321-8","journal-title":"J Cheminform"},{"issue":"11","key":"480_CR26","doi-asserted-by":"publisher","first-page":"1104","DOI":"10.1002\/jms.4278","volume":"53","author":"J-A Sch\u00fcler","year":"2018","unstructured":"Sch\u00fcler J-A, Neumann S, M\u00fcller-Hannemann M, Brandt W (2018) Chemfrag: chemically meaningful annotation of fragment ion mass spectra. J Mass Spectrom 53(11):1104\u20131115. https:\/\/doi.org\/10.1002\/jms.4278","journal-title":"J Mass Spectrom"},{"issue":"7","key":"480_CR27","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"JW Raymond","year":"2002","unstructured":"Raymond JW, Willett P (2002) Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J Comput Aided Mol Des 16(7):521\u2013533. https:\/\/doi.org\/10.1023\/A:1021271615909","journal-title":"J Comput Aided Mol Des"}],"container-title":["Journal of Cheminformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13321-020-00480-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13321-020-00480-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13321-020-00480-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,17]],"date-time":"2020-12-17T09:14:45Z","timestamp":1608196485000},"score":1,"resource":{"primary":{"URL":"https:\/\/jcheminf.biomedcentral.com\/articles\/10.1186\/s13321-020-00480-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["480"],"URL":"https:\/\/doi.org\/10.1186\/s13321-020-00480-1","relation":{},"ISSN":["1758-2946"],"issn-type":[{"type":"electronic","value":"1758-2946"}],"subject":[],"published":{"date-parts":[[2020,12]]},"assertion":[{"value":"20 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"73"}}