| Rotamer optimization for protein design through MAP estimation and problem-size reduction. | |
| | |
MedLine Citation:
|
PMID: 19123203 Owner: NLM Status: MEDLINE |
Abstract/OtherAbstract:
|
The search for the global minimum energy conformation (GMEC) of protein side chains is an important computational challenge in protein structure prediction and design. Using rotamer models, the problem is formulated as a NP-hard optimization problem. Dead-end elimination (DEE) methods combined with systematic A* search (DEE/A*) has proven useful, but may not be strong enough as we attempt to solve protein design problems where a large number of similar rotamers is eligible and the network of interactions between residues is dense. In this work, we present an exact solution method, named BroMAP (branch-and-bound rotamer optimization using MAP estimation), for such protein design problems. The design goal of BroMAP is to be able to expand smaller search trees than conventional branch-and-bound methods while performing only a moderate amount of computation in each node, thereby reducing the total running time. To achieve that, BroMAP attempts reduction of the problem size within each node through DEE and elimination by lower bounds from approximate maximum-a-posteriori (MAP) estimation. The lower bounds are also exploited in branching and subproblem selection for fast discovery of strong upper bounds. Our computational results show that BroMAP tends to be faster than DEE/A* for large protein design cases. BroMAP also solved cases that were not solved by DEE/A* within the maximum allowed time, and did not incur significant disadvantage for cases where DEE/A* performed well. Therefore, BroMAP is particularly applicable to large protein design problems where DEE/A* struggles and can also substitute for DEE/A* in general GMEC search. |
| | |
Authors:
|
Eun-Jong Hong; Shaun M Lippow; Bruce Tidor; Tomás Lozano-Pérez |
Related Documents
:
|
15386283 - Anatomy of the nasal cavity and paranasal sinuses in aegyptopithecus and early miocene ... 11308453 - Entropy-based analysis of the number partitioning problem. 2107853 - Referrals to a hearing aid clinic: scope for improvement. |
Publication Detail:
|
Type: Journal Article |
Journal Detail:
|
Title: Journal of computational chemistry Volume: 30 ISSN: 1096-987X ISO Abbreviation: J Comput Chem Publication Date: 2009 Sep |
Date Detail:
|
Created Date: 2009-07-01 Completed Date: 2009-11-02 Revised Date: 2011-04-11 |
Medline Journal Info:
|
Nlm Unique ID: 9878362 Medline TA: J Comput Chem Country: United States |
Other Details:
|
Languages: eng Pagination: 1923-45 Citation Subset: IM |
Copyright Information:
|
Copyright 2009 Wiley Periodicals, Inc. |
Affiliation:
|
Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA. |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
Algorithms* Computer Simulation Protein Conformation Proteins / chemistry* |
| Grant Support | |
ID/Acronym/Agency:
|
R01 GM065418-07/GM/NIGMS NIH HHS |
| Chemical | |
Reg. No./Substance:
|
0/Proteins |
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Interaction of NO molecules with Pd clusters: Ab initio density-functional study.
Next Document: Charge transport in stacking metal and metal-free phthalocyanine iodides. Effects of packing, dopant...