Hockenmaier Julia, Joshi Aravind K, Dill Ken A
Institute for Research in Cognitive Science and Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104-6228, USA.
Proteins. 2007 Jan 1;66(1):1-15. doi: 10.1002/prot.21195.
An important puzzle in structural biology is the question of how proteins are able to fold so quickly into their unique native structures. There is much evidence that protein folding is hierarchic. In that case, folding routes are not linear, but have a tree structure. Trees are commonly used to represent the grammatical structure of natural language sentences, and chart parsing algorithms efficiently search the space of all possible trees for a given input string. Here we show that one such method, the CKY algorithm, can be useful both for providing novel insight into the physical protein folding process, and for computational protein structure prediction. As proof of concept, we apply this algorithm to the HP lattice model of proteins. Our algorithm identifies all direct folding route trees to the native state and allows us to construct a simple model of the folding process. Despite its simplicity, our model provides an account for the fact that folding rates depend only on the topology of the native state but not on sequence composition.
结构生物学中的一个重要谜题是蛋白质如何能够如此迅速地折叠成其独特的天然结构。有大量证据表明蛋白质折叠是分层进行的。在这种情况下，折叠路径不是线性的，而是具有树状结构。树通常用于表示自然语言句子的语法结构，并且图表解析算法可以有效地在给定输入字符串的所有可能树的空间中进行搜索。在这里，我们表明一种这样的方法，即CKY算法，对于深入了解蛋白质折叠的物理过程以及用于计算蛋白质结构预测都可能是有用的。作为概念验证，我们将此算法应用于蛋白质的HP晶格模型。我们的算法识别出所有通向天然状态的直接折叠路径树，并使我们能够构建一个简单的折叠过程模型。尽管我们的模型很简单，但它解释了折叠速率仅取决于天然状态的拓扑结构而不取决于序列组成这一事实。
