Protein structure prediction via combinatorial assembly of sub-structural units.
Following the hierarchical nature of protein folding, we propose a three-stage scheme for the prediction of a protein structure from its sequence. First, the sequence is cut to fragments that are each assigned a structure. Second, the assigned structures are combinatorially assembled to form the overall 3D organization. Third, highly ranked predicted arrangements are completed and refined. This work focuses on the second stage of this scheme: the combinatorial assembly. We present CombDock, a combinatorial docking algorithm. CombDock gets an ordered set of protein sub-structures and predicts the inter-contacts that define their overall organization. We reduce the combinatorial assembly to a graph-theory problem, and give a heuristic polynomial solution to this computationally hard problem. We applied CombDock to various examples of structural units of two types: protein domains and building blocks, which are relatively stable sub-structures of domains. Moreover, we tested CombDock using increasingly distorted input, where the native structural units were replaced by similarly folded units extracted from homologous proteins and, in the more difficult cases, from globally unrelated proteins. The algorithm is robust, showing low sensitivity to input distortion. This suggests that CombDock is a useful tool in protein structure prediction that may be applied to large target proteins.
Inbar
Yuval
Y
School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. inbaryuv@tau.ac.il
Benyamini
Hadar
H
Nussinov
Ruth
R
Wolfson
Haim J
HJ
D000465:Algorithms; D001665:Binding Sites; D020650:Combinatorial Chemistry Techniques / Q000379:methods*; D003198:Computer Simulation; D005964:Glucosyltransferases / Q000737:chemistry; D008956:Models, Chemical; D008958:Models, Molecular; D011485:Protein Binding; D011487:Protein Conformation; D017434:Protein Structure, Tertiary; D021122:Protein Subunits; D011506:Proteins / Q000737:chemistry*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017386:Sequence Homology, Amino Acid
D021122:Protein Subunits; D011506:Proteins; D005964:Glucosyltransferases; C019963:cyclomaltodextrin glucanotransferase