Rensselaer Polytechnic Institute has been awarded a grant to develop predictive models for protein structures. Proteins are chains of amino acids that fold into complex forms (in three dimensions) in order to function. Bystroff and colleagues have written a program called SCALI (for Structural Core ALIgnment) that aligns proteins that share a certain part of their folding arrangement (regardless of their sequential ordering) and then clusters these alignments to find the recurrent themes. The results show that all protein folds can be described as a small set of folding arrangements, or cores, and that each core has characteristic patterns of amino acid preferences. To model these, the alignments are converted to a set of hidden Markov models (HMM). In this project new algorithms will be developed to deal with the specific problems associated with "self-avoiding" HMMs. A heuristic method will be used to find the most probable path (according to the models), while an exact solution is proposed for the sum over all self-avoiding paths. The exact solution has many potential applications for other methods using HMMs.
