{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T15:07:31Z","timestamp":1722697651244},"reference-count":34,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2004,3,24]],"date-time":"2004-03-24T00:00:00Z","timestamp":1080086400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[2004,5]]},"abstract":"Abstract<\/jats:title>Graph theory offers a convenient and highly attractive approach to various tasks of pattern recognition. Provided there is a graph representation of the object in question (e.g. a chemical structure or protein fold), the recognition procedure is reduced to the problem of common subgraph isomorphism (CSI). Complexity of this problem shows combinatorial dependence on the size of input graphs, which in many practical cases makes the approach computationally intractable. Among the optimal algorithms for CSI, the leading place in practice belongs to algorithms based on maximal clique detection in the association graph. Backtracking algorithms for CSI, first developed two decades ago, are rarely used. We propose an improved backtracking algorithm for CSI, which differs from its predecessors by better search strategy and is therefore more efficient. We found that the new algorithm outperforms the traditional maximal clique approach by orders of magnitude in computational time. Copyright \u00a9 2004 John Wiley & Sons, Ltd.<\/jats:p>","DOI":"10.1002\/spe.588","type":"journal-article","created":{"date-parts":[[2004,4,2]],"date-time":"2004-04-02T17:03:04Z","timestamp":1080925384000},"page":"591-607","source":"Crossref","is-referenced-by-count":68,"title":["Common subgraph isomorphism detection by backtracking search"],"prefix":"10.1002","volume":"34","author":[{"given":"Evgeny B.","family":"Krissinel","sequence":"first","affiliation":[]},{"given":"Kim","family":"Henrick","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2004,3,24]]},"reference":[{"key":"e_1_2_1_2_2","first-page":"177","volume-title":"Applications of Graph Theory","author":"Rouvray DH","year":"1979"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(90)90312-A"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1993.1074"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/jcc.540050105"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008034527445"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0008-6215(97)00196-1"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1021\/ci990262o"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1021\/ci00031a005"},{"key":"e_1_2_1_10_2","first-page":"703","article-title":"Graph modeling of metabolism","volume":"15","author":"Arita M","year":"2000","journal-title":"Journal of the Japanese Society of Artificial Intelligence"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1021\/ci00020a030"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1021\/ja00465a041"},{"key":"e_1_2_1_13_2","first-page":"1","article-title":"Structure\u2013reactivity maps as a tool for visualizing xenobiotic structure\u2013reactivity relationships","volume":"2","author":"Gifford E","year":"1996","journal-title":"Network Science"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016387816342"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/S1093-3263(00)00061-9"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.42855"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.809105"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0262-8856(89)90008-5"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.1996.0512"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(00)00048-0"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021271615909"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45129-3_2"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02575586"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380120103"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321925"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkg065"},{"key":"e_1_2_1_28_2","first-page":"1955","article-title":"The CCP4 molecular\u2010graphics project","volume":"58","author":"Potterton E","year":"2002","journal-title":"Acta Crystallography"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/28.1.235"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-70659-3_12"},{"key":"e_1_2_1_31_2","first-page":"149","volume-title":"Proceedings of the 3rd IAPR\u2010TC\u201015 International Workshop on Graph\u2010based Representations","author":"Cordella LP","year":"2001"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.682179"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001498000415"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/69.842269"},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1107\/S0907444994003112"}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.588","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.588","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,17]],"date-time":"2023-11-17T05:50:45Z","timestamp":1700200245000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.588"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3,24]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,5]]}},"alternative-id":["10.1002\/spe.588"],"URL":"http:\/\/dx.doi.org\/10.1002\/spe.588","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,3,24]]}}}
