Dynamic Programming for ab-initio Prediction of Protein Folding Routes

Workshop on Topology: Identifying Order in Complex Systems
Topic:Dynamic Programming for ab-initio Prediction of Protein Folding Routes
Speaker:Julia Hockemaier
Affiliation:University of Illinois
Date:Wednesday, November 7
Time/Room:2:30pm - 3:30pm/David Rittenhouse Lab.(Room A8), University of Pennsylvania

I will demonstrate how the Cocke-Kasami-Younger (CKY) algorithm, a standard dynamic programming technique that is normally used in natural language parsing, can be adapted to give us novel insights into the protein folding problem. If we assume that folding is a greedy, hierarchical search for lowest-energy structures, CKY provides an efficient way to find all direct folding routes. I will also show that we can extend CKY to construct a Markov chain model of the entire folding process, and that this Markov chain may explain an apparent contradiction between what experimentalists observe in a test tube and what many theorists predict.