{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,30]],"date-time":"2022-12-30T06:53:34Z","timestamp":1672383214109},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,2]]},"abstract":"Automated reaction mapping is a fundamental first step in the analysis of chemical reactions and opens the door to the development of sophisticated chemical kinetic tools. This article formulates the reaction mapping problem as an optimization problem. The problem is shown to be NP-Complete for general graphs. Five algorithms based on canonical graph naming and enumerative combinatoric techniques are developed to solve the problem. Unlike previous formulations based on limited configurations or classifications, our algorithms are uniquely capable of mapping any reaction that can be represented as a set of chemical graphs optimally. This is due to the direct use of Graph Isomorphism as the basis for these algorithms as opposed to the more commonly used Maximum Common Subgraph. Experimental results on chemical and biological reaction databases demonstrate the efficiency of our algorithms.<\/jats:p>","DOI":"10.1145\/1412228.1498697","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":15,"title":["Automated reaction mapping"],"prefix":"10.1145","volume":"13","author":[{"given":"John D.","family":"Crabtree","sequence":"first","affiliation":[{"name":"University of North Alabama"}]},{"given":"Dinesh P.","family":"Mehta","sequence":"additional","affiliation":[{"name":"Colorado School of Mines"}]}],"member":"320","published-online":{"date-parts":[[2009,2,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Aho A. Hopcroft J. and Ullman J. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA. Aho A. Hopcroft J. and Ullman J. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley Reading MA."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1089\/1066527041410337"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci700433d"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808746"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90292-I"},{"key":"e_1_2_1_6_1","unstructured":"Blower P. E. and Dana R. C. 1986. Creation of a chemical reaction database from the primary literature. In Modern Approaches to Chemical Reaction Searching P. Willett Ed. Gower 146--164. Blower P. E. and Dana R. C. 1986. Creation of a chemical reaction database from the primary literature. In Modern Approaches to Chemical Reaction Searching P. Willett Ed. Gower 146--164."},{"key":"e_1_2_1_7_1","first-page":"1301","article-title":"Identification of symmetries in molecules and complexes","volume":"44","author":"Chen W.","year":"2004","unstructured":"Chen , W. , Huang , J. , and Gilson , M. K. 2004 . Identification of symmetries in molecules and complexes . Journal of Chemical Information and Modeling 44 , 4, 1301 -- 1313 . Chen, W., Huang, J., and Gilson, M. K. 2004. Identification of symmetries in molecules and complexes. Journal of Chemical Information and Modeling 44, 4, 1301--1313.","journal-title":"Journal of Chemical Information and Modeling"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.3390\/61100915"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-2180(97)00282-4"},{"key":"e_1_2_1_12_1","first-page":"432","article-title":"Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs","volume":"38","author":"Faulon J.-L.","year":"1998","unstructured":"Faulon , J.-L. 1998 . Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs . Journal of Chemical Information and Modeling 38 , 3, 432 -- 444 . Faulon, J.-L. 1998. Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs. Journal of Chemical Information and Modeling 38, 3, 432--444.","journal-title":"Journal of Chemical Information and Modeling"},{"key":"e_1_2_1_13_1","unstructured":"Faulon J.-L. 2007a. http:\/\/www.cs.sandia.gov\/~jfaulon\/QSAR\/downloads.html. Faulon J.-L. 2007a. http:\/\/www.cs.sandia.gov\/~jfaulon\/QSAR\/downloads.html."},{"key":"e_1_2_1_14_1","unstructured":"Faulon J.-L. 2007b. Private email conversation with regarding time complexity of author's algorithms. Faulon J.-L. 2007b. Private email conversation with regarding time complexity of author's algorithms."},{"key":"e_1_2_1_15_1","first-page":"427","article-title":"The signature molecular descriptor. 4. canonizing molecules using extended valence sequences","volume":"44","author":"Faulon J.-L.","year":"2004","unstructured":"Faulon , J.-L. , Collins , M. J. , and Carr , R. D. 2004 . The signature molecular descriptor. 4. canonizing molecules using extended valence sequences . Journal of Chemical Information and Modeling 44 , 2, 427 -- 436 . Faulon, J.-L., Collins, M. J., and Carr, R. D. 2004. The signature molecular descriptor. 4. canonizing molecules using extended valence sequences. Journal of Chemical Information and Modeling 44, 2, 427--436.","journal-title":"Journal of Chemical Information and Modeling"},{"key":"e_1_2_1_16_1","volume-title":"Proc. 6th Int. Symp. Computational Biology and Genome Informatics. 1209--1212","author":"Felix L.","unstructured":"Felix , L. and Valiente , G . 2005. Efficient validation of metabolic pathway databases . In Proc. 6th Int. Symp. Computational Biology and Genome Informatics. 1209--1212 . Felix, L. and Valiente, G. 2005. Efficient validation of metabolic pathway databases. In Proc. 6th Int. Symp. Computational Biology and Genome Informatics. 1209--1212."},{"key":"e_1_2_1_17_1","unstructured":"Garey M. R. and Johnson D. S. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York. Garey M. R. and Johnson D. S. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. New York."},{"key":"e_1_2_1_18_1","volume-title":"Eds","author":"Gasteiger J.","year":"2003","unstructured":"Gasteiger , J. and Engel , T. , Eds . 2003 . Chemoinformatics : A Textbook. Wiley . Gasteiger, J. and Engel, T., Eds. 2003. Chemoinformatics: A Textbook. Wiley."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/14.7.591"},{"key":"e_1_2_1_20_1","volume-title":"Group-Theoretic Algorithms and Graph Isomorphism","author":"Hoffmann C. M.","unstructured":"Hoffmann , C. M. 1982. Group-Theoretic Algorithms and Graph Isomorphism . Springer-Verlag Berlin and Heidelberg GmbH and Co. KG. Hoffmann, C. M. 1982. Group-Theoretic Algorithms and Graph Isomorphism. Springer-Verlag Berlin and Heidelberg GmbH and Co. KG."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803896"},{"key":"e_1_2_1_22_1","unstructured":"Institute G. R. 2006. Gri-mech 3.0. http:\/\/www.me.berkeley.edu\/gri-mech\/. Institute G. R. 2006. Gri-mech 3.0. http:\/\/www.me.berkeley.edu\/gri-mech\/."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/anie.198004953"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1515\/znb-1982-0921"},{"key":"e_1_2_1_25_1","volume-title":"The Art of Computer Programming","author":"Knuth D. E.","unstructured":"Knuth , D. E. 2005. The Art of Computer Programming , Volume 4 , Fascicle 3: Generating All Combinations and Partitions. Addison-Wesley Professional . Knuth, D. E. 2005. The Art of Computer Programming, Volume 4, Fascicle 3: Generating All Combinations and Partitions. Addison-Wesley Professional."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci7004324"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1135\/cccc19841090"},{"key":"e_1_2_1_28_1","first-page":"2284","article-title":"Mathematical model of organic history. iii. reactions graphs","volume":"48","author":"Kvasnicka V.","year":"1983","unstructured":"Kvasnicka , V. , Kratochvil , M. , and Koca , J. 1983 . Mathematical model of organic history. iii. reactions graphs . Collection of Czechoslovak Chemical Communications 48 , 8, 2284 -- 2304 . Kvasnicka, V., Kratochvil, M., and Koca, J. 1983. Mathematical model of organic history. iii. reactions graphs. Collection of Czechoslovak Chemical Communications 48, 8, 2284--2304.","journal-title":"Collection of Czechoslovak Chemical Communications"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-1280(91)85270-H"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci60015a009"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380120103"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci00031a005"},{"key":"e_1_2_1_34_1","volume-title":"Congressus Numerantium 30","author":"McKay B.","year":"1981","unstructured":"McKay , B. 1981 . Practical graph isomorphism . Congressus Numerantium 30 , 45--87. McKay, B. 1981. Practical graph isomorphism. Congressus Numerantium 30, 45--87."},{"key":"e_1_2_1_35_1","unstructured":"McKay B. 2004. No automorphisms yes? http:\/\/cs.anu.edu.au\/~bdm\/nauty\/. McKay B. 2004. No automorphisms yes? http:\/\/cs.anu.edu.au\/~bdm\/nauty\/."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/028\/14"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Moock T. E. Nourse J. G. Grier D. and Hounshell W. D. 1988. The implementation of atom-atom mapping and related features in the reaction access system (reaccs). In Chemical structures W. A. Warr Ed. Springer Verlag 303--313. Moock T. E. Nourse J. G. Grier D. and Hounshell W. D. 1988. The implementation of atom-atom mapping and related features in the reaction access system (reaccs). In Chemical structures W. A. Warr Ed. Springer Verlag 303--313.","DOI":"10.1007\/978-3-642-73975-0_33"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1021\/c160017a018"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Pemmaraju S. and Skiena S. 2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press New York. Pemmaraju S. and Skiena S. 2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press New York.","DOI":"10.1017\/CBO9781139164849"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/45.6.631"},{"key":"e_1_2_1_41_1","first-page":"7","article-title":"Maximum common subgraph isomorphism algorithms for the matching of chemical structures","volume":"16","author":"Raymond J. W.","year":"2002","unstructured":"Raymond , J. W. and Willett , P. 2002 . Maximum common subgraph isomorphism algorithms for the matching of chemical structures . Journal of Computer-Aided Molecular Design 16 , 7 (July), 521--533. Raymond, J. W. and Willett, P. 2002. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of Computer-Aided Molecular Design 16, 7 (July), 521--533.","journal-title":"Journal of Computer-Aided Molecular Design"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1021\/ci00017a001"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Vleduts G. E. 1963. Concerning one system of classification and codification of organic reactions. Information Storage and Retrieval 117--146. Vleduts G. E. 1963. Concerning one system of classification and codification of organic reactions. Information Storage and Retrieval 117--146.","DOI":"10.1016\/0020-0271(63)90013-5"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1412228.1498697","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:56:15Z","timestamp":1672304175000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1412228.1498697"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2]]},"references-count":43,"alternative-id":["10.1145\/1412228.1498697"],"URL":"http:\/\/dx.doi.org\/10.1145\/1412228.1498697","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[2009,2]]}}}