Fully automated protein complex prediction based on topological similarity and community structure

To understand the function of protein complexes and their association with biological processes, a lot of studies have been done towards analyzing the protein-protein interaction (PPI) networks. However, the advancement in high-throughput technology has resulted in a humongous amount of data for analysis. Moreover, high level of noise, sparseness, and skewness in degree distribution of PPI networks limits the performance of many clustering algorithms and further analysis of their interactions.In addressing and solving these problems we present a novel random walk based algorithm that converts the incomplete and binary PPI network into a protein-protein topological similarity matrix (PP-TS matrix). We believe that if two proteins share some high-order topological similarities they are likely to be interacting with each other. Using the obtained PP-TS matrix, we constructed and used weighted networks to further study and analyze the interaction among proteins. Specifically, we applied a fully automated community structure finding algorithm (Auto-HQcut) on the obtained weighted network to cluster protein complexes. We then analyzed the protein complexes for significance in biological processes. To help visualize and analyze these protein complexes we also developed an interface that displays the resulting complexes as well as the characteristics associated with each complex.Applying our approach to a yeast protein-protein interaction network, we found that the predicted protein-protein interaction pairs with high topological similarities have more significant biological relevance than the original protein-protein interactions pairs. When we compared our PPI network reconstruction algorithm with other existing algorithms using gene ontology and gene co-expression, our algorithm produced the highest similarity scores. Also, our predicted protein complexes showed higher accuracy measure compared to the other protein complex predictions.     

Predicting where Small Molecules Bind at Protein-Protein Interfaces

Small molecules that bind at protein-protein interfaces may either block or stabilize protein-protein interactions in cells. Thus, some of these binding interfaces may turn into prospective targets for drug design. Here, we collected 175 pairs of protein-protein (PP) complexes and protein-ligand (PL) complexes with known three-dimensional structures for which (1) one protein from the PP complex shares at least 40% sequence identity with the protein from the PL complex, and (2) the interface regions of these proteins overlap at least partially with each other. We found that those residues of the interfaces that may bind the other protein as well as the small molecule are evolutionary more conserved on average, have a higher tendency of being located in pockets and expose a smaller fraction of their surface area to the solvent than the remaining protein-protein interface region. Based on these findings we derived a statistical classifier that predicts patches at binding interfaces that have a higher tendency to bind small molecules. We applied this new prediction method to more than 10 000 interfaces from the protein data bank. For several complexes related to apoptosis the predicted binding patches were in direct contact to co-crystallized small molecules.     

An expectation/maximization nuclear vector replacement algorithm for automated NMR resonance assignments

We report an automated procedure for high-throughput NMR resonance assignment for a protein of known structure, or of an homologous structure. Our algorithm performs Nuclear Vector Replacement (NVR) by Expectation/Maximization (EM) to compute assignments. NVR correlates experimentally-measured NH residual dipolar couplings (RDCs) and chemical shifts to a given a priori whole-protein 3D structural model. The algorithm requires only uniform (15)N-labelling of the protein, and processes unassigned H(N)-(15)N HSQC spectra, H(N)-(15)N RDCs, and sparse H(N)-H(N) NOE's (d(NN)s). NVR runs in minutes and efficiently assigns the (H(N),(15)N) backbone resonances as well as the sparse d(NN)s from the 3D (15)N-NOESY spectrum, in O (n(3)) time. The algorithm is demonstrated on NMR data from a 76-residue protein, human ubiquitin, matched to four structures, including one mutant (homolog), determined either by X-ray crystallography or by different NMR experiments (without RDCs). NVR achieves an average assignment accuracy of over 99%. We further demonstrate the feasibility of our algorithm for different and larger proteins, using different combinations of real and simulated NMR data for hen lysozyme (129 residues) and streptococcal protein G (56 residues), matched to a variety of 3D structural models.     

Rapid identification of protein-protein interfaces for the construction of a complex model based on multiple unassigned signals by using time-sharing NMR measurements

Protein-protein interactions are necessary for various cellular processes, and therefore, information related to protein-protein interactions and structural information of complexes is invaluable. To identify protein-protein interfaces using NMR, resonance assignments are generally necessary to analyze the data; however, they are time consuming to collect, especially for large proteins. In this paper, we present a rapid, effective, and unbiased approach for the identification of a protein-protein interface without resonance assignments. This approach requires only a single set of 2D titration experiments of a single protein sample, labeled with a unique combination of an (15)N-labeled amino acid and several amino acids (13)C-labeled on specific atoms. To rapidly obtain high resolution data, we applied a new pulse sequence for time-shared NMR measurements that allowed simultaneous detection of a ω(1)-TROSY-type backbone (1)H-(15)N and aromatic (1)H-(13)C shift correlations together with single quantum methyl (1)H-(13)C shift correlations. We developed a structure-based computational approach, that uses our experimental data to search the protein surfaces in an unbiased manner to identify the residues involved in the protein-protein interface. Finally, we demonstrated that the obtained information of the molecular interface could be directly leveraged to support protein-protein docking studies. Such rapid construction of a complex model provides valuable information and enables more efficient biochemical characterization of a protein-protein complex, for instance, as the first step in structure-guided drug development.     

A quantitative analysis of interfacial amino acid conservation in protein-protein hetero complexes

A long-standing question in molecular biology is whether interfaces of protein-protein complexes are more conserved than the rest of the protein surfaces. Although it has been reported that conservation can be used as an indicator for predicting interaction sites on proteins, there are recent reports stating that the interface regions are only slightly more conserved than the rest of the protein surfaces, with conservation signals not being statistically significant enough for predicting protein-protein binding sites. In order to properly address these controversial reports we have studied a set of 28 well resolved hetero complex structures of proteins that consists of transient and non-transient complexes. The surface positions were classified into four conservation classes and the conservation index of the surface positions was quantitatively analyzed. The results indicate that the surface density of highly conserved positions is significantly higher in the protein-protein interface regions compared with the other regions of the protein surface. However, the average conservation index of the patches in the interface region is not significantly higher compared with other surface regions of the protein structures. This finding demonstrates that the number of conserved residue positions is a more appropriate indicator for predicting protein-protein binding sites than the average conservation index in the interacting region. We have further validated our findings on a set of 59 benchmark complex structures. Furthermore, an analysis of 19 complexes of antigen-antibody interactions shows that there is no conservation of amino acid positions in the interacting regions of these complexes, as expected, with the variable region of the immunoglobulins interacting mostly with the antigens. Interestingly, antigen interacting regions also have a higher number of non-conserved residue positions in the interacting region than the rest of the protein surface.     

Integrated analysis of multiple data sources reveals modular structure of biological networks

It has been a challenging task to integrate high-throughput data into investigations of the systematic and dynamic organization of biological networks. Here, we presented a simple hierarchical clustering algorithm that goes a long way to achieve this aim. Our method effectively reveals the modular structure of the yeast protein-protein interaction network and distinguishes protein complexes from functional modules by integrating high-throughput protein-protein interaction data with the added subcellular localization and expression profile data. Furthermore, we take advantage of the detected modules to provide a reliably functional context for the uncharacterized components within modules. On the other hand, the integration of various protein-protein association information makes our method robust to false-positives, especially for derived protein complexes. More importantly, this simple method can be extended naturally to other types of data fusion and provides a framework for the study of more comprehensive properties of the biological network and other forms of complex networks.     

Prediction of interface residues in protein-protein complexes by a consensus neural network method: test against NMR data

The number of structures of protein-protein complexes deposited to the Protein Data Bank is growing rapidly. These structures embed important information for predicting structures of new protein complexes. This motivated us to develop the PPISP method for predicting interface residues in protein-protein complexes. In PPISP, sequence profiles and solvent accessibility of spatially neighboring surface residues were used as input to a neural network. The network was trained on native interface residues collected from the Protein Data Bank. The prediction accuracy at the time was 70% with 47% coverage of native interface residues. Now we have extensively improved PPISP. The training set now consisted of 1156 nonhomologous protein chains. Test on a set of 100 nonhomologous protein chains showed that the prediction accuracy is now increased to 80% with 51% coverage. To solve the problem of over-prediction and under-prediction associated with individual neural network models, we developed a consensus method that combines predictions from multiple models with different levels of accuracy and coverage. Applied on a benchmark set of 68 proteins for protein-protein docking, the consensus approach outperformed the best individual models by 3-8 percentage points in accuracy. To demonstrate the predictive power of cons-PPISP, eight complex-forming proteins with interfaces characterized by NMR were tested. These proteins are nonhomologous to the training set and have a total of 144 interface residues identified by chemical shift perturbation. cons-PPISP predicted 174 interface residues with 69% accuracy and 47% coverage and promises to complement experimental techniques in characterizing protein-protein interfaces. .     

Structural similarity and classification of protein interaction interfaces

Interactions between proteins play a key role in many cellular processes. Studying protein-protein interactions that share similar interaction interfaces may shed light on their evolution and could be helpful in elucidating the mechanisms behind stability and dynamics of the protein complexes. When two complexes share structurally similar subunits, the similarity of the interaction interfaces can be found through a structural superposition of the subunits. However, an accurate detection of similarity between the protein complexes containing subunits of unrelated structure remains an open problem. Here, we present an alignment-free machine learning approach to measure interface similarity. The approach relies on the feature-based representation of protein interfaces and does not depend on the superposition of the interacting subunit pairs. Specifically, we develop an SVM classifier of similar and dissimilar interfaces and derive a feature-based interface similarity measure. Next, the similarity measure is applied to a set of 2,806×2,806 binary complex pairs to build a hierarchical classification of protein-protein interactions. Finally, we explore case studies of similar interfaces from each level of the hierarchy, considering cases when the subunits forming interactions are either homologous or structurally unrelated. The analysis has suggested that the positions of charged residues in the homologous interfaces are not necessarily conserved and may exhibit more complex conservation patterns.     

A polynomial-time nuclear vector replacement algorithm for automated NMR resonance assignments.

High-throughput NMR structural biology can play an important role in structural genomics. We report an automated procedure for high-throughput NMR resonance assignment for a protein of known structure, or of a homologous structure. These assignments are a prerequisite for probing protein-protein interactions, protein-ligand binding, and dynamics by NMR. Assignments are also the starting point for structure determination and refinement. A new algorithm, called Nuclear Vector Replacement (NVR) is introduced to compute assignments that optimally correlate experimentally measured NH residual dipolar couplings (RDCs) to a given a priori whole-protein 3D structural model. The algorithm requires only uniform( 15)N-labeling of the protein and processes unassigned H(N)-(15)N HSQC spectra, H(N)-(15)N RDCs, and sparse H(N)-H(N) NOE's (d(NN)s), all of which can be acquired in a fraction of the time needed to record the traditional suite of experiments used to perform resonance assignments. NVR runs in minutes and efficiently assigns the (H(N),(15)N) backbone resonances as well as the d(NN)s of the 3D (15)N-NOESY spectrum, in O(n(3)) time. The algorithm is demonstrated on NMR data from a 76-residue protein, human ubiquitin, matched to four structures, including one mutant (homolog), determined either by x-ray crystallography or by different NMR experiments (without RDCs). NVR achieves an assignment accuracy of 92-100%. We further demonstrate the feasibility of our algorithm for different and larger proteins, using NMR data for hen lysozyme (129 residues, 97-100% accuracy) and streptococcal protein G (56 residues, 100% accuracy), matched to a variety of 3D structural models. Finally, we extend NVR to a second application, 3D structural homology detection, and demonstrate that NVR is able to identify structural homologies between proteins with remote amino acid sequences using a database of structural models.     

Docking without docking: ISEARCH--prediction of interactions using known interfaces

The increasing number of solved protein structures provides a solid number of interfaces, if protein-protein interactions, domain-domain contacts, and contacts between biological units are taken into account. An interface library gives us the opportunity to identify surface regions on a target molecule that are similar by local structure and residue composition. If both unbound components of a possible protein complex exhibit structural similarities to a known interface, the unbound structures can be superposed onto the known interfaces. The approach is accompanied by two mathematical problems. Protein surfaces have to be quickly screened by thousands of patches, and similarity has to be evaluated by a suitable scoring scheme. The used algorithm (NeedleHaystack) identifies similar patches within minutes. Structurally related sites are recognized even if only parts of the template patches are structurally related to the interface region. A successful prediction of the protein complex depends on a suitable template of the library. However, the performed tests indicate that interaction sites are identified even if the similarity is very low. The approach complements existing ab initio methods and provides valuable results on standard benchmark sets.     

An NMR method for the determination of protein binding interfaces using TEMPOL-induced chemical shift perturbations

Background

The determination of protein–protein interfaces is of crucial importance to understand protein function and to guide the design of compounds. To identify protein–protein interface by NMR spectroscopy, ¹³C NMR paramagnetic shifts induced by freely diffusing 4-hydroxy-2, 2, 6, 6-tetramethyl-piperidine-1-oxyl (TEMPOL) are promising, because TEMPOL affects distinct ¹³C NMR chemical shifts of the solvent accessible nuclei belonging to proteins of interest, while ¹³C nuclei within the interior of the proteins may be distinguished by a lack of such shifts.

Method

We measured the ¹³C NMR paramagnetic shifts induced by TEMPOL by recording ¹³C–¹³C TOCSY spectra for ubiquitin in the free state and the complex state with yeast ubiquitin hydrolase1 (YUH1).

Results

Upon complexation of ubiquitin with YUH1, ¹³C NMR paramagnetic shifts associated with the protein binding interface were reduced by 0.05 ppm or more. The identified interfacial atoms agreed with the prior X-ray crystallographic data.

Conclusions

The TEMPOL-induced ¹³C chemical shift perturbation is useful to determine precise protein–protein interfaces.

General significance

The present method is a useful method to determine protein–protein interface by NMR, because it has advantages in easy sample preparations, simple data analyses, and wide applicabilities.     

A new, structurally nonredundant, diverse data set of protein-protein interfaces and its implications

Here, we present a diverse, structurally nonredundant data set of two-chain protein-protein interfaces derived from the PDB. Using a sequence order-independent structural comparison algorithm and hierarchical clustering, 3799 interface clusters are obtained. These yield 103 clusters with at least five nonhomologous members. We divide the clusters into three types. In Type I clusters, the global structures of the chains from which the interfaces are derived are also similar. This cluster type is expected because, in general, related proteins associate in similar ways. In Type II, the interfaces are similar; however, remarkably, the overall structures and functions of the chains are different. The functional spectrum is broad, from enzymes/inhibitors to immunoglobulins and toxins. The fact that structurally different monomers associate in similar ways, suggests "good" binding architectures. This observation extends a paradigm in protein science: It has been well known that proteins with similar structures may have different functions. Here, we show that it extends to interfaces. In Type III clusters, only one side of the interface is similar across the cluster. This structurally nonredundant data set provides rich data for studies of protein-protein interactions and recognition, cellular networks and drug design. In particular, it may be useful in addressing the difficult question of what are the favorable ways for proteins to interact. (The data set is available at http://protein3d.ncifcrf.gov/~keskino/ and http://home.ku.edu.tr/~okeskin/INTERFACE/INTERFACES.html.)     

Mapping of protein-protein interaction sites by the 'absence of interference' approach

Protein-protein interactions are critical to most biological processes, and locating protein-protein interfaces on protein structures is an important task in molecular biology. We developed a new experimental strategy called the ‘absence of interference’ approach to determine surface residues involved in protein-protein interaction of established yeast two-hybrid pairs of interacting proteins. One of the proteins is subjected to high-level randomization by error-prone PCR. The resulting library is selected by yeast two-hybrid system for interacting clones that are isolated and sequenced. The interaction region can be identified by an absence or depletion of mutations. For data analysis and presentation, we developed a Web interface that analyzes the mutational spectrum and displays the mutational frequency on the surface of the structure (or a structural model) of the randomized protein†. Additionally, this interface might be of use for the display of mutational distributions determined by other types of random mutagenesis experiments. We applied the approach to map the interface of the catalytic domain of the DNA methyltransferase Dnmt3a with its regulatory factor Dnmt3L. Dnmt3a was randomized with high mutational load. A total of 76 interacting clones were isolated and sequenced, and 648 mutations were identified. The mutational pattern allowed to identify a unique interaction region on the surface of Dnmt3a, which comprises about 500-600 Å². The results were confirmed by site-directed mutagenesis and structural analysis. The absence-of-interference approach will allow high-throughput mapping of protein interaction sites suitable for functional studies and protein docking.     

A combinatorial score to distinguish biological and nonbiological protein-protein interfaces

With the large amount of protein-protein complex structural data available, to understand the key features governing the specificity of protein-protein recognition and to define a suitable scoring function for protein-protein interaction predictions, we have analyzed the protein interfaces from geometric and energetic points of view. Atom-based potential of mean force (PMFScore), packing density, contact size, and geometric complementarity are calculated for crystal contacts in 74 homodimers and 91 monomers, which include real biological interactions in dimers and nonbiological contacts in monomers and dimers. Simple cutoffs were developed for single and combinatorial parameters to distinguish biological and nonbiological contacts. The results show that PMFScore is a better discriminator between biological and nonbiological interfaces comparable in size. The combination of PMFScore and contact size is the most powerful pairwise discriminator. A combinatorial score (CFPScore) based on the four parameters was developed, which gives the success rate of the homodimer discrimination of 96.6% and error rate of the monomer discrimination of 6.0% and 19.8% according to Valdar's and our definition, respectively. Compared with other statistical learning models, the cutoffs for the four parameters and their combinations are directly based on physical models, simple, and can be easily applied to protein-protein interface analysis and docking studies.     

Electrostatics-defying interaction between arginine termini as a thermodynamic driving force in protein-protein interaction

Apparent electrostatics-defying clustering of arginines attributed as screening effect of solvent is in this study examined as a possible thermodynamic driving force in protein-protein interaction. A dataset of 266 protein dimers is found to have approximately 22% arginines mutually paired and approximately 17% pairs in interaction across interfaces and thus putative "hotspots" of protein-protein interaction. The pairing, uncorrelated with inter or intramolecular context, could be contributing in protein folding as well, and, uncorrelated with solvent access, could be driven by effects that are generic to solvent and protein structures. Mutually stacked at shorter distances but in diverse geometrical modes otherwise, the cations tend to be in gross deficit of hydrogen-bond partners, and contributing electrostatics across protein-protein interface that, on average, is repulsive for protein-protein interaction. Embedded in local environment enriched in polarizable residues, aromatic, aliphatic, and anionic, the arginines may contribute to protein-protein interaction via environmental polarization response to electrostatics of cation clustering, a possible new principle in molecular recognition.     

Dissecting protein-protein recognition sites

The recognition sites in 70 pairwise protein-protein complexes of known three-dimensional structure are dissected in a set of surface patches by clustering atoms at the interface. When the interface buries <2000 A2 of protein surface, the recognition sites usually form a single patch on the surface of each component protein. In contrast, larger interfaces are generally multipatch, with at least one pair of patches that are equivalent in size to a single-patch interface. Each recognition site, or patch within a site, contains a core made of buried interface atoms, surrounded by a rim of atoms that remain accessible to solvent in the complex. A simple geometric model reproduces the number and distribution of atoms within a patch. The rim is similar in composition to the rest of the protein surface, but the core has a distinctive amino acid composition, which may help in identifying potential protein recognition sites on single proteins of known structures.     

Application of automated NOE assignment to three-dimensional structure refinement of a 28 kDa single-chain T cell receptor

An automated procedure for NOE assignment and three-dimensional structure refinement is presented. The input to the procedure consists of (1) an ensemble of preliminary protein NMR structures, (2) partial sequence-specific assignments for the protein and (3) the positions and volumes of unassigned NOESY cross peaks. Chemical shifts for unassigned side chain protons are predicted from the preliminary structures. The chemical shifts and unassigned NOESY cross peaks are input to an automated procedure for NOE assignment and structure calculation (ARIA) [Nilges et al. (1997) J. Mol. Biol., 269, 408–422]. ARIA is optimized for the task of structure refinement of larger proteins. Errors are filtered to ensure that sequence-specific assignments are reliable. The procedure is applied to the 27.8 kDa single-chain T cell receptor (scTCR). Preliminary NMR structures, nearly complete backbone assignments, partial assignments of side chain protons and more than 1300 unassigned NOESY cross peaks are input. Using the procedure, the resonant frequencies of more than 40 additional side chain protons are assigned. Over 400 new NOE cross peaks are assigned unambiguously. Distances derived from the automatically assigned NOEs improve the precision and quality of calculated scTCR structures. In the refined structures, a hydrophobic cluster of side chains on the scTCR surface that binds major histocompatibility complex (MHC)/antigen is revealed. It is composed of the side chains of residues from three loops and stabilizes the conformation of residues that interact with MHC.     

A de novo protein binding pair by computational design and directed evolution

The de novo design of protein-protein interfaces is a stringent test of our understanding of the principles underlying protein-protein interactions and would enable unique approaches to biological and medical challenges. Here we describe a motif-based method to computationally design protein-protein complexes with native-like interface composition and interaction density. Using this method we designed a pair of proteins, Prb and Pdar, that heterodimerize with a Kd of 130 nM, 1000-fold tighter than any previously designed de novo protein-protein complex. Directed evolution identified two point mutations that improve affinity to 180 pM. Crystal structures of an affinity-matured complex reveal binding is entirely through the designed interface residues. Surprisingly, in the in vitro evolved complex one of the partners is rotated 180° relative to the original design model, yet still maintains the central computationally designed hotspot interaction and preserves the character of many peripheral interactions. This work demonstrates that high-affinity protein interfaces can be created by designing complementary interaction surfaces on two noninteracting partners and underscores remaining challenges.