We present a novel approach for predicting protein folding kinetics using techniques from the field of model checking. This represents the first time model checking has been applied to a problem in the field of structural biology. The protein's energy landscape is encoded symbolically using Binary decision diagrams and related data structures. Questions regarding the kinetics of folding are encoded as formulas in the temporal logic CTL. Model checking algorithms are then used to make quantitative predictions about the kinetics of folding. We show that our approach scales to state spaces as large as 10²³ when using exact algorithms for model checking. This is at least 14 orders of magnitude larger than the number of configurations considered by comparable techniques. Furthermore,our approach scales to state spaces at least as large as 10³² unique configurations when using approximation algorithms for model checking. We tested our method on 19 test proteins. The quantitative predictions regarding folding rates for these test proteins are in good agreement with experimentally measured values, achieving a correlation coefficient of 0.87.

17 pages

*Department of Computer Science and Department of Biological Sciences, Carnegie Mellon University

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu