Dynamic programming for ab-initio prediction of protein folding routes
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.
Julia Hockenmaier is Assistant Professor, Computer Science at University of Illinois at Urbana Champaign. For more information, please see http://www.cs.uiuc.edu/~juliahmr/.