Thesis defense: Exact Rotamer Optimization for Computational Protein Design
Speaker: Eun-Jong Hong , MIT CSAIL
Date: May 16 2008
Time: 11:00AM to 12:00PM
Location: 32-D463 (Star)
Contact: Teresa Cataldo, 617-452-5005, cataldo@csail.mit.edu
Relevant URL:
The search for the global minimum energy conformation (GMEC) of
protein side chains is an important computational challenge in protein
structure prediction and design. In particular, we are interested in
finding the GMEC for protein design, where a fixed backbone scaffold
is given, but the amino-acid sequence that will most stably folds to
the scaffold is to be determined. In our approach, such a sequence is
found by identifying the side-chain conformation of each amino acid
that minimizes the sum of interaction energies for a given energy
model.
Despite the continuous nature of a protein side chain's degrees of
freedom, the problem is formulated as a discrete search problem by
approximating each side chain's conformational space with a finite
number of fixed conformations called rotamers. Among many algorithmic
investigations to solve the resulting NP-hard optimization problem
exactly, dead-end elimination (DEE) combined with systematic A* search
(DEE/A*) have proven most useful in finding the GMEC for protein
design problems. However, DEE/A* may still not be strong enough as we
attempt to address many current and future challenges in protein
design such as protein design using large and dense rotamer libraries,
protein-protein interface design, and de novo protein design. These
protein design problems often reduce to a GMEC search problem where a
large number of similar rotamers is eligible at each design position
and the network of interactions between residues is dense.
In this talk, we present a new exact solution algorithm, 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
rotamer and rotamer-pair elimination by lower bounds from approximate
maximum-a-posteriori (MAP) estimation. It also employs additional
problem-size reduction techniques such as rotamer contraction and DEE
in the branch-and-bound framework. The lower bounds from MAP
estimation are also exploited in branching and subproblem selection
for fast discovery of strong upper bounds and effective pruning of
non-optimal nodes.
Our computational results show that BroMAP usually finds the solution
faster than DEE/A* for larger protein design cases. BroMAP also
solves cases that were not previously solvable by DEE/A* on a single
workstation within the maximum allowed time of 7 days. In addition,
BroMAP does not incur any significant disadvantage for cases where
DEE/A* performs well. Therefore, BroMAP extends the size limit of
GMEC search problems that can be addressed using limited computational
resources, and it can substitute for DEE/A* in general GMEC search.
See other events that are part of
See other events happening in May 2008
