{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:53Z","timestamp":1750308773243,"version":"3.41.0"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            M. Word and coauthors from the Richardsons' 3D Protein Structure laboratory at Duke University propose\n            <jats:italic>dot scores<\/jats:italic>\n            to measure interatomic interactions in molecular structures. Their program REDUCE uses these scores in a brute-force search to solve instances of the\n            <jats:italic>NP<\/jats:italic>\n            -hard problem of finding the optimal placement of hydrogen atoms in molecular structures determined by X-ray crystallography. We capture the central combinatorial optimization in the hydrogen placement problem with an abstraction that we call an interaction (hyper)graph. REDUCE's dot-based scoring function cannot be decomposed into the sum of pair interactions, but because the function is short ranged we are able to decompose it into the sum of single, pair, triple, and quadruple interactions that we represent by graph hyperedges. Almost every interaction graph we have observed has had a small treewidth. This fact allows us to replace the brute-force search by dynamic programming, giving speedups of nearly ten orders of magnitude. This dynamic programming has been incorporated into REDUCE and is available for download.\n          <\/jats:p>","DOI":"10.1145\/1227161.1227167","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"1-16","source":"Crossref","is-referenced-by-count":0,"title":["Faster placement of hydrogens in protein structures by dynamic programming"],"prefix":"10.1145","volume":"12","author":[{"given":"Andrew","family":"Leaver-Fay","sequence":"first","affiliation":[{"name":"Computer Science, UNC Chapel Hill, Chapel Hill, North Carolina"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuanxin","family":"Liu","sequence":"additional","affiliation":[{"name":"Computer Science, UNC Chapel Hill, Chapel Hill, North Carolina"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[{"name":"Computer Science, UNC Chapel Hill, Chapel Hill, North Carolina"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xueyi","family":"Wang","sequence":"additional","affiliation":[{"name":"Computer Science, UNC Chapel Hill, Chapel Hill, North Carolina"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,6,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0607033"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"volume-title":"Proc. 15th Int. Colloq. Automata, Languages and Programming","author":"Bodlaender H. L.","key":"e_1_2_1_4_1","unstructured":"Bodlaender, H. L. 1988. Dynamic programming on graphs with bounded treewidth. In Proc. 15th Int. Colloq. Automata, Languages and Programming. Springer Verlag, Lecture Notes in Computer Science 317, Tampere, Finland, 105--118."},{"key":"e_1_2_1_5_1","unstructured":"Branden C. and Tooze J. 1999. Introduction to protein structure Second ed. Garland Publishing."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/356539a0"},{"key":"e_1_2_1_7_1","volume-title":"Pacific Symposium on Biocomputing","author":"Leaver-Fay A.","year":"2005","unstructured":"Leaver-Fay, A., Kuhlman, B., and Snoeyink, J. 2005. An adaptive dynamic programming algorithm for the side chain placement problem. In Pacific Symposium on Biocomputing, 2005. World Scientific, The Big Island, HI, 17--28."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/prot.10286"},{"key":"e_1_2_1_9_1","unstructured":"Richardson D. C. and Richardson J. S. 2001. Mage probe and kinemages. Vol. F. Kluwer Publishers Dordrecht."},{"key":"e_1_2_1_10_1","unstructured":"Richardson J. S. and Richardson D. 1987. Some design principles: betabellin. In Protein Engineering D. Oxender and C. Fox Eds. Alan R. Liss Inc. New York 149--163 340--341."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11557067_31"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1110\/ps.9.11.2251"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1998.2400"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1998.2401"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1227167","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1227161.1227167","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:37Z","timestamp":1750278157000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1227161.1227167"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":14,"alternative-id":["10.1145\/1227161.1227167"],"URL":"https:\/\/doi.org\/10.1145\/1227161.1227167","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}