Clark D A, Shirazi J, Rawlings C J
Biomedical Computing Unit, Imperial Cancer Research Fund Laboratories, London, UK.
Protein Eng. 1991 Oct;4(7):751-60. doi: 10.1093/protein/4.7.751.
An algorithm for predicting protein alpha/beta-sheet topologies from secondary structure and topological folding rules (constraints) has been developed and implemented in Prolog. This algorithm (CBS1) is based on constraint satisfaction and employs forward pruned breadth-first search and rotational invariance. CBS1 showed a 37-fold increase in efficiency over an exhaustive generate and test algorithm giving the same solution for a typical sheet of five strands whose topology was predicted from secondary structure with four topological folding constraints. Prolog specifications of a range of putative protein folding rules were then used to (i) replicate published protein topology predictions and (ii) validate these rules against known protein structures of nucleotide-binding domains. This demonstrated that (i) manual techniques for topology prediction can lead to non-exhaustive search and (ii) most of these protein folding principles were violated by specific proteins. Various extensions to the algorithm are discussed.
一种用于根据二级结构和拓扑折叠规则（约束条件）预测蛋白质α/β折叠拓扑结构的算法已被开发出来，并在Prolog中实现。该算法（CBS1）基于约束满足，采用前向剪枝广度优先搜索和旋转不变性。对于一个由五条链组成的典型折叠，其拓扑结构是根据二级结构和四个拓扑折叠约束条件预测出来的，与一种穷举生成并测试的算法相比，CBS1的效率提高了37倍，且能给出相同的解决方案。然后，使用一系列假定的蛋白质折叠规则的Prolog规范来（i）复制已发表的蛋白质拓扑结构预测结果，以及（ii）根据核苷酸结合结构域的已知蛋白质结构来验证这些规则。这表明（i）用于拓扑结构预测的手工技术可能导致非穷举搜索，以及（ii）这些蛋白质折叠原理中的大多数都被特定蛋白质所违背。文中还讨论了该算法的各种扩展。
