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.     

Prediction of multimolecular assemblies by multiple docking

The majority of proteins function when associated in multimolecular assemblies. Yet, prediction of the structures of multimolecular complexes has largely not been addressed, probably due to the magnitude of the combinatorial complexity of the problem. Docking applications have traditionally been used to predict pairwise interactions between molecules. We have developed an algorithm that extends the application of docking to multimolecular assemblies. We apply it to predict quaternary structures of both oligomers and multi-protein complexes. The algorithm predicted well a near-native arrangement of the input subunits for all cases in our data set, where the number of the subunits of the different target complexes varied from three to ten. In order to simulate a more realistic scenario, unbound cases were tested. In these cases the input conformations of the subunits are either unbound conformations of the subunits or a model obtained by a homology modeling technique. The successful predictions of the unbound cases, where the input conformations of the subunits are different from their conformations within the target complex, suggest that the algorithm is robust. We expect that this type of algorithm should be particularly useful to predict the structures of large macromolecular assemblies, which are difficult to solve by experimental structure determination.     

Predicting oligomeric assemblies: N-mers a primer

Multi-protein complexes play key roles in many biological processes. However, since the structures of these assemblies are hard to resolve experimentally, the detailed mechanism of how they work cooperatively in the cell has remained elusive. Similarly, recent advances on in silico prediction of protein-protein interactions have so far avoided this difficult problem. In this paper, we present a general algorithm to predict molecular assemblies of homo-oligomers. Given the number of N-mers and the 3D structure of one monomer, the method samples all the possible symmetries that N-mers can be assembled. Based on a scoring function that clusters the low free energy structures at each binding interface, the algorithm predicts the complex structure as well as the symmetry of the protein assembly. The method is quite general and does not involve any free parameters. The algorithm has been implemented as a public server and integrated to the protein-protein complex prediction server ClusPro. Using this application, we validated predictions for trimers, tetramers (discriminating between dimer of dimers and 4-fold symmetry structures), pentamers and hexamers (discriminating between trimer of dimers, dimer of trimers, and 6-fold symmetry structures), for a total of 107 assemblies. For 85% of the multimers, the server predicts the complex structure within an average rms deviation of 2A from the full crystal. For complexes that involve more than one binding interface, the cluster size at each surface provides a strong indication as to which interface forms first. With improving scoring functions and computer power, our multimer docking approach could be used as a framework to address the more general problem of multi-protein assemblies.     

Multi-LZerD: multiple protein docking for asymmetric complexes

The tertiary structures of protein complexes provide a crucial insight about the molecular mechanisms that regulate their functions and assembly. However, solving protein complex structures by experimental methods is often more difficult than single protein structures. Here, we have developed a novel computational multiple protein docking algorithm, Multi‐LZerD, that builds models of multimeric complexes by effectively reusing pairwise docking predictions of component proteins. A genetic algorithm is applied to explore the conformational space followed by a structure refinement procedure. Benchmark on eleven hetero‐multimeric complexes resulted in near‐native conformations for all but one of them (a root mean square deviation smaller than 2.5Å). We also show that our method copes with unbound docking cases well, outperforming the methodology that can be directly compared with our approach. Multi‐LZerD was able to predict near‐native structures for multimeric complexes of various topologies.Proteins 2012; © 2012 Wiley Periodicals, Inc.     

A flexible docking approach for prediction of T cell receptor–peptide–MHC complexes

T cell receptors (TCRs) are immune proteins that specifically bind to antigenic molecules, which are often foreign peptides presented by major histocompatibility complex proteins (pMHCs), playing a key role in the cellular immune response. To advance our understanding and modeling of this dynamic immunological event, we assembled a protein–protein docking benchmark consisting of 20 structures of crystallized TCR/pMHC complexes for which unbound structures exist for both TCR and pMHC. We used our benchmark to compare predictive performance using several flexible and rigid backbone TCR/pMHC docking protocols. Our flexible TCR docking algorithm, TCRFlexDock, improved predictive success over the fixed backbone protocol, leading to near‐native predictions for 80% of the TCR/pMHC cases among the top 10 models, and 100% of the cases in the top 30 models. We then applied TCRFlexDock to predict the two distinct docking modes recently described for a single TCR bound to two different antigens, and tested several protein modeling scoring functions for prediction of TCR/pMHC binding affinities. This algorithm and benchmark should enable future efforts to predict, and design of uncharacterized TCR/pMHC complexes.     

Prediction of RNA pseudoknots using heuristic modeling with mapping and sequential folding

Predicting RNA secondary structure is often the first step to determining the structure of RNA. Prediction approaches have historically avoided searching for pseudoknots because of the extreme combinatorial and time complexity of the problem. Yet neglecting pseudoknots limits the utility of such approaches. Here, an algorithm utilizing structure mapping and thermodynamics is introduced for RNA pseudoknot prediction that finds the minimum free energy and identifies information about the flexibility of the RNA. The heuristic approach takes advantage of the 5' to 3' folding direction of many biological RNA molecules and is consistent with the hierarchical folding hypothesis and the contact order model. Mapping methods are used to build and analyze the folded structure for pseudoknots and to add important 3D structural considerations. The program can predict some well known pseudoknot structures correctly. The results of this study suggest that many functional RNA sequences are optimized for proper folding. They also suggest directions we can proceed in the future to achieve even better results.     

Accelerating protein docking in ZDOCK using an advanced 3D convolution library

Computational prediction of the 3D structures of molecular interactions is a challenging area, often requiring significant computational resources to produce structural predictions with atomic-level accuracy. This can be particularly burdensome when modeling large sets of interactions, macromolecular assemblies, or interactions between flexible proteins. We previously developed a protein docking program, ZDOCK, which uses a fast Fourier transform to perform a 3D search of the spatial degrees of freedom between two molecules. By utilizing a pairwise statistical potential in the ZDOCK scoring function, there were notable gains in docking accuracy over previous versions, but this improvement in accuracy came at a substantial computational cost. In this study, we incorporated a recently developed 3D convolution library into ZDOCK, and additionally modified ZDOCK to dynamically orient the input proteins for more efficient convolution. These modifications resulted in an average of over 8.5-fold improvement in running time when tested on 176 cases in a newly released protein docking benchmark, as well as substantially less memory usage, with no loss in docking accuracy. We also applied these improvements to a previous version of ZDOCK that uses a simpler non-pairwise atomic potential, yielding an average speed improvement of over 5-fold on the docking benchmark, while maintaining predictive success. This permits the utilization of ZDOCK for more intensive tasks such as docking flexible molecules and modeling of interactomes, and can be run more readily by those with limited computational resources.     

On the Structural Diversity and Individuality of Polymorphic Amyloid Protein Assemblies

The prediction of highly ordered three-dimensional structures of amyloid protein fibrils from the amino acid sequences of their monomeric self-assembly precursors constitutes a challenging and unresolved aspect of the classical protein folding problem. Because of the polymorphic nature of amyloid assembly whereby polypeptide chains of identical amino acid sequences under identical conditions are capable of self-assembly into a spectrum of different fibril structures, the prediction of amyloid structures from an amino acid sequence requires a detailed and holistic understanding of its assembly free energy landscape. The full extent of the structure space accessible to the cross-β molecular architecture of amyloid must also be resolved. Here, we review the current understanding of the diversity and the individuality of amyloid structures, and how the polymorphic landscape of amyloid links to biology and disease phenotypes. We present a comprehensive review of structural models of amyloid fibrils derived by cryo-EM, ssNMR and AFM to date, and discuss the challenges ahead for resolving the structural basis and the biological consequences of polymorphic amyloid assemblies.     

Using restraints in EROS-DOCK improves model quality in pairwise and multicomponent protein docking

Protein docking algorithms aim to predict the 3D structure of a protein complex from the structures of its separated components. In the past, most docking algorithms focused on docking pairs of proteins to form dimeric complexes. However, attention is now turning towards the more difficult problem of using docking methods to predict the structures of multicomponent complexes. In both cases, however, the constituent proteins often change conformation upon complex formation, and this can cause many algorithms to fail to detect near-native binding orientations due to the high number of atomic steric clashes in the list of candidate solutions. An increasingly popular way to retain more near-native orientations is to define one or more restraints that serve to modulate or override the effect of steric clashes. Here, we present an updated version of our “EROS-DOCK” docking algorithm which has been extended to dock arbitrary dimeric and trimeric complexes, and to allow the user to define residue-residue or atom-atom interaction restraints. Our results show that using even just one residue-residue restraint in each interaction interface is sufficient to increase the number of cases with acceptable solutions within the top 10 from 51 to 121 out of 173 pairwise docking cases, and to successfully dock 8 out of 11 trimeric complexes.     

Structural analysis of flexible proteins in solution by small angle X-ray scattering combined with crystallography

In the last few years, SAXS of biological materials has been rapidly evolving and promises to move structural analysis to a new level. Recent innovations in SAXS data analysis allow ab initio shape predictions of proteins in solution. Furthermore, experimental scattering data can be compared to calculated scattering curves from the growing data base of solved structures and also identify aggregation and unfolded proteins. Combining SAXS results with atomic resolution structures enables detailed characterizations in solution of mass, radius, conformations, assembly, and shape changes associated with protein folding and functions. SAXS can efficiently reveal the spatial organization of protein domains, including domains missing from or disordered in known crystal structures, and establish cofactor or substrate-induced conformational changes. For flexible domains or unstructured regions that are not amenable for study by many other structural techniques, SAXS provides a unique technology. Here, we present SAXS shape predictions for PCNA that accurately predict a trimeric ring assembly and for a full-length DNA repair glycosylase with a large unstructured region. These new results in combination with illustrative published data show how SAXS combined with high resolution crystal structures efficiently establishes architectures, assemblies, conformations, and unstructured regions for proteins and protein complexes in solution.     

Protein tertiary structure modeling driven by deep learning and contact distance prediction in CASP13

Predicting residue-residue distance relationships (eg, contacts) has become the key direction to advance protein structure prediction since 2014 CASP11 experiment, while deep learning has revolutionized the technology for contact and distance distribution prediction since its debut in 2012 CASP10 experiment. During 2018 CASP13 experiment, we enhanced our MULTICOM protein structure prediction system with three major components: contact distance prediction based on deep convolutional neural networks, distance-driven template-free (ab initio) modeling, and protein model ranking empowered by deep learning and contact prediction. Our experiment demonstrates that contact distance prediction and deep learning methods are the key reasons that MULTICOM was ranked 3rd out of all 98 predictors in both template-free and template-based structure modeling in CASP13. Deep convolutional neural network can utilize global information in pairwise residue-residue features such as coevolution scores to substantially improve contact distance prediction, which played a decisive role in correctly folding some free modeling and hard template-based modeling targets. Deep learning also successfully integrated one-dimensional structural features, two-dimensional contact information, and three-dimensional structural quality scores to improve protein model quality assessment, where the contact prediction was demonstrated to consistently enhance ranking of protein models for the first time. The success of MULTICOM system clearly shows that protein contact distance prediction and model selection driven by deep learning holds the key of solving protein structure prediction problem. However, there are still challenges in accurately predicting protein contact distance when there are few homologous sequences, folding proteins from noisy contact distances, and ranking models of hard targets.     

A combinatorial approach to protein docking with flexible side chains.

Rigid-body docking approaches are not sufficient to predict the structure of a protein complex from the unbound (native) structures of the two proteins. Accounting for side chain flexibility is an important step towards fully flexible protein docking. This work describes an approach that allows conformational flexibility for the side chains while keeping the protein backbone rigid. Starting from candidates created by a rigid-docking algorithm, we demangle the side chains of the docking site, thus creating reasonable approximations of the true complex structure. These structures are ranked with respect to the binding free energy. We present two new techniques for side chain demangling. Both approaches are based on a discrete representation of the side chain conformational space by the use of a rotamer library. This leads to a combinatorial optimization problem. For the solution of this problem, we propose a fast heuristic approach and an exact, albeit slower, method that uses branch-and-cut techniques. As a test set, we use the unbound structures of three proteases and the corresponding protein inhibitors. For each of the examples, the highest-ranking conformation produced was a good approximation of the true complex structure.     

基于最小自由能和协变信息预测带伪结RNA二级结构的迭代化方法

多数RNA分子的结构在进化中是高度保守的, 其中很多包含伪结。而RNA伪结的预测一直是一个棘手问题, 很多RNA 二级结构预测算法都不能预测伪结。文章提出一种基于迭代法预测带伪结RNA 二级结构的新方法。该方法在给潜在碱基对打分时综合了热力学和协变信息, 通过基于最小自由能RNA折叠算法的多次迭代选出所有的碱基对。测试结果表明: 此方法几乎能预测到所有的伪结。与其他方法相比, 敏感度接近最优, 而特异性达到最优。     

Ab initio modeling of the herpesvirus VP26 core domain assessed by CryoEM density

Efforts in structural biology have targeted the systematic determination of all protein structures through experimental determination or modeling. In recent years, 3-D electron cryomicroscopy (cryoEM) has assumed an increasingly important role in determining the structures of these large macromolecular assemblies to intermediate resolutions (6–10 Å). While these structures provide a snapshot of the assembly and its components in well-defined functional states, the resolution limits the ability to build accurate structural models. In contrast, sequence-based modeling techniques are capable of producing relatively robust structural models for isolated proteins or domains. In this work, we developed and applied a hybrid modeling approach, utilizing cryoEM density and ab initio modeling to produce a structural model for the core domain of a herpesvirus structural protein, VP26. Specifically, this method, first tested on simulated data, utilizes the cryoEM density map as a geometrical constraint in identifying the most native-like models from a gallery of models generated by ab initio modeling. The resulting model for the core domain of VP26, based on the 8.5-Å resolution herpes simplex virus type 1 (HSV-1) capsid cryoEM structure and mutational data, exhibited a novel fold. Additionally, the core domain of VP26 appeared to have a complementary interface to the known upper-domain structure of VP5, its cognate binding partner. While this new model provides for a better understanding of the assembly and interactions of VP26 in HSV-1, the approach itself may have broader applications in modeling the components of large macromolecular assemblies.     

Characterization and comparison of protein structures. Part II-comparison.

The Fourier methods are applied to the pairwise comparison of Calpha-backbones in protein structures. The technique allows to assess both the general similarity and the main origins of resemblance (coincident periodicities, similarity of fragments, or large-scale semblance of folding). The analogous methods can be extended to the study of correlations between the structural characteristics for the Calpha-backbone of one protein and the distribution of physico-chemical parameters along the primary amino acid sequence for the other. Finally, we discuss the problem of clusterization of pairwise data into tree-like hierarchical system.     

Screening a peptidyl database for potential ligands to proteins with side-chain flexibility

The three key challenges addressed in our development of SPECITOPE , a tool for screening large structural databases for potential ligands to a protein, are to eliminate infeasible candidates early in the search, incorporate ligand and protein side-chain flexibility upon docking, and provide an appropriate rank for potential new ligands. The protein ligand-binding site is modeled by a shell of surface atoms and by hydrogen-bonding template points for the ligand to match, conferring specificity to the interaction. SPECITOPE combinatorially matches all hydrogen-bond donors and acceptors of the screened molecules to the template points. By eliminating molecules that cannot match distance or hydrogen-bond constraints, the transformation of potential docking candidates into the ligand-binding site and the shape and hydrophobic complementarity evaluations are only required for a small subset of the database. SPECITOPE screens 140,000 peptide fragments in about an hour and has identified and docked known inhibitors and potential new ligands to the free structures of four distinct targets: a serine protease, a DNA repair enzyme, an aspartic proteinase, and a glycosyltransferase. For all four, protein side-chain rotations were critical for successful docking, emphasizing the importance of inducible complementarity for accurately modeling ligand interactions. SPECITOPE has a range of potential applications for understanding and engineering protein recognition, from inhibitor and linker design to protein docking and macromolecular assembly. Proteins 33:74–87, 1998. © 1998 Wiley-Liss, Inc.     

Parser for protein folding units

General patterns of protein structural organization have emerged from studies of hundreds of structures elucidated by X-ray crystallography and nuclear magnetic resonance. Structural units are commonly identified by visual inspection of molecular models using qualitative criteria. Here, we propose an algorithm for identification of structural units by objective, quantitative criteria based on atomic interactions. The underlying physical concept is maximal interactions within each unit and minimal interaction between units (domains). In a simple harmonic approximation, interdomain dynamics is determined by the strength of the interface and the distribution of masses. The most likely domain decomposition involves units with the most correlated motion, or largest interdomain fluctuation time. The decomposition of a convoluted 3-D structure is complicated by the possibility that the chain can cross over several times between units. Grouping the residues by solving an eigenvalue problem for the contact matrix reduces the problem to a one-dimensional search for all reasonable trial bisections. Recursive bisection yields a tree of putative folding units. Simple physical criteria are used to identify units that could exist by themselves. The units so defined closely correspond to crystallographers' notion of structural domains. The results are useful for the analysis of folding principles, for modular protein design and for protein engineering. © 1994 Wiley-Liss, Inc.