NDLI: Faster placement of hydrogens in protein structures by dynamic programming

Please wait, while we are loading the content...

Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks

An experimental study of sorting and branch prediction

Terracost: Computing least-cost-path surfaces for massive grid terrains

A graph approach to the threshold all-against-all substring matching problem

A dictionary implementation based on dynamic perfect hashing

Preface

Engineering a cache-oblivious sorting algorithm

Sum-of-squares heuristics for bin packing and memory allocation

Efficient models for timetable information in public transportation systems

Faster placement of hydrogens in protein structures by dynamic programming

Papers from ALENEX 2005

On the adaptiveness of Quicksort

An experimental study of different approaches to solve the market equilibrium problem

Better external memory suffix array construction

Approximating the true evolutionary distance between two genomes

Faster placement of hydrogens in protein structures by dynamic programming

Content Provider	ACM Digital Library
Author	Leaver-Fay, Andrew Liu, Yuanxin Snoeyink, Jack Wang, Xueyi
Copyright Year	2008
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.
Starting Page	1
Ending Page	16
Page Count	16
File Format	PDF
ISSN	10846654
e-ISSN	10846654
DOI	10.1145/1227161.1227167
Journal	Journal of Experimental Algorithmics (JEA)
Volume Number	12
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-12
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Dynamic programming Hard-sphere model Hydrogen bonds Hydrogen placement Protein structure Treewidth
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Investigating hydrogen bonds in liquid ethylene glycol structure by means of molecular dynamics

Solving problems on recursively constructed graphs

Monadic datalog over finite structures of bounded treewidth

Does Treewidth Help in Modal Satisfiability?

Structure-based evaluation of the regioselectivity in bifurcated hydrogen bonds

On exact algorithms for treewidth

Faster Algorithms for Algebraic Path Properties in RSMs with Constant Treewidth

Hard Sphere Simulator : Visualization and modelling of atomic structures

Crystal and Molecular Structures of Phosphonolactone Derivatives of Chromone

Faster placement of hydrogens in protein structures by dynamic programming

Similar Documents

Investigating hydrogen bonds in liquid ethylene glycol structure by means of molecular dynamics

Solving problems on recursively constructed graphs

Monadic datalog over finite structures of bounded treewidth

Does Treewidth Help in Modal Satisfiability?

Structure-based evaluation of the regioselectivity in bifurcated hydrogen bonds

On exact algorithms for treewidth

Faster Algorithms for Algebraic Path Properties in RSMs with Constant Treewidth

Hard Sphere Simulator : Visualization and modelling of atomic structures

Crystal and Molecular Structures of Phosphonolactone Derivatives of Chromone

Faster placement of hydrogens in protein structures by dynamic programming