Thursday, February 1, 2007
4:15 pm
B17 Upson Hall

Computer Science
Spring 2007

Ken A. Dill
University of California, San Francisco

Protein Folding as a Global Optimization Problem

The computer-based prediction of protein structures from their monomer sequences is of considerable interest for accelerating drug discovery. In protein structure prediction, the goal is to find a single globally optimal solution in a search space that grows exponentially with the number of degrees of freedom. We have explored various methods. One approach is based on a strategy we call "zipping & assembly", which derives from knowledge of the physical routes of protein folding. Another approach is based on a similarity between the way proteins fold and the CKY algorithm that is used by computational linguists to parse sentences. These methods usually find the globally optimal state (known from simple toy model problems), and they do so fairly efficiently.