Exact rotamer optimization for computational protein design
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | eng |
| Published: |
Massachusetts Institute of Technology
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/44421 |
| _version_ | 1826200502388391936 |
|---|---|
| author | Hong, Eun-Jong, 1975- |
| author2 | Tomás Lozano-Pérez. |
| author_facet | Tomás Lozano-Pérez. Hong, Eun-Jong, 1975- |
| author_sort | Hong, Eun-Jong, 1975- |
| collection | MIT |
| description | Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. |
| first_indexed | 2024-09-23T11:37:28Z |
| format | Thesis |
| id | mit-1721.1/44421 |
| institution | Massachusetts Institute of Technology |
| language | eng |
| last_indexed | 2024-09-23T11:37:28Z |
| publishDate | 2009 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/444212019-04-11T08:53:52Z Exact rotamer optimization for computational protein design Hong, Eun-Jong, 1975- Tomás Lozano-Pérez. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. Electrical Engineering and Computer Science. Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008. Includes bibliographical references (leaves 235-244). 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*) have 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 thesis, 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 energy lower bounds from approximate maximurn-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 solvable by DEE/A* within the maximum allowed time, and did not incur significant disadvantage for cases where DEE/A* performed well. In the second part of the thesis, we explore several ways of improving the energy lower bounds by using Lagrangian relaxation. Through computational experiments, solving the dual problem derived from cyclic subgraphs, such as triplets, is shown to produce stronger lower bounds than using the tree-reweighted max-product algorithm. (cont.) In the second approach, the Lagrangian relaxation is tightened through addition of violated valid inequalities. Finally, we suggest a way of computing individual lower bounds using the dual method. The preliminary results from evaluating BroMAP employing the dual bounds suggest that the use of the strengthened bounds does not in general improve the running time of BroMAP due to the longer running time of the dual method. by Eun-Jong Hong. Ph.D. 2009-01-30T16:44:48Z 2009-01-30T16:44:48Z 2008 2008 Thesis http://hdl.handle.net/1721.1/44421 289408979 eng M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission. http://dspace.mit.edu/handle/1721.1/7582 244 leaves application/pdf Massachusetts Institute of Technology |
| spellingShingle | Electrical Engineering and Computer Science. Hong, Eun-Jong, 1975- Exact rotamer optimization for computational protein design |
| title | Exact rotamer optimization for computational protein design |
| title_full | Exact rotamer optimization for computational protein design |
| title_fullStr | Exact rotamer optimization for computational protein design |
| title_full_unstemmed | Exact rotamer optimization for computational protein design |
| title_short | Exact rotamer optimization for computational protein design |
| title_sort | exact rotamer optimization for computational protein design |
| topic | Electrical Engineering and Computer Science. |
| url | http://hdl.handle.net/1721.1/44421 |
| work_keys_str_mv | AT hongeunjong1975 exactrotameroptimizationforcomputationalproteindesign |