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.