  The computation of the global minimum energy conformation (GMEC) is an
important and challenging topic in structure-based computational protein
design. In this paper, we propose a new protein design algorithm based on the
AND/OR branch-and-bound (AOBB) search, which is a variant of the traditional
branch-and-bound search algorithm, to solve this combinatorial optimization
problem. By integrating with a powerful heuristic function, AOBB is able to
fully exploit the graph structure of the underlying residue interaction network
of a backbone template to significantly accelerate the design process. Tests on
real protein data show that our new protein design algorithm is able to solve
many prob- lems that were previously unsolvable by the traditional exact search
algorithms, and for the problems that can be solved with traditional provable
algorithms, our new method can provide a large speedup by several orders of
magnitude while still guaranteeing to find the global minimum energy
conformation (GMEC) solution.
