Protein topology prediction through constraint-based search and the evaluation of topological folding rules

An algorithm for predicting protein /ß-sheet topologiesfrom secondary structure and topological folding rules (constraints)has been developed and implemented in Prolog. This algorithm(CBS1) is based on constraint satisfaction and employs forwardpruned breadth-first search and rotational invariance. CBS1showed a 37-fold increase in efficiency over an exhaustive generateand test algorithm giving the same solution for a typical sheetof five strands whose topology was predicted from secondarystructure with four topological folding constraints. Prologspecifications of a range of putative protein folding ruleswere then used to (i) replicate published protein topology predictionsand (ii) validate these rules against known protein structuresof nucleotide-binding domains. This demonstrated that (i) manualtechniques for topology prediction can lead to non-exhaustivesearch and (ii) most of these protein folding principles wereviolated by specific proteins. Various extensions to the algorithmare discussed.