Access Restriction

Author Leaver-Fay, Andrew ♦ Liu, Yuanxin ♦ Snoeyink, Jack ♦ Wang, Xueyi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2008
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Dynamic programming ♦ Hard-sphere model ♦ Hydrogen bonds ♦ Hydrogen placement ♦ Protein structure ♦ Treewidth
Abstract M. Word and coauthors from the Richardsons' 3D Protein Structure laboratory at Duke University propose dot scores to measure interatomic interactions in molecular structures. Their program REDUCE uses these scores in a brute-force search to solve instances of the $\textit{NP}-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.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2008-06-12
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 12
Page Count 16
Starting Page 1
Ending Page 16

Open content in new tab

   Open content in new tab
Source: ACM Digital Library