Estimating gene regulatory networks and protein-protein interactions of Saccharomyces cerevisiae from multiple genome-wide data

MOTIVATION: Biological processes in cells are properly performed by gene regulations, signal transductions and interactions between proteins. To understand such molecular networks, we propose a statistical method to estimate gene regulatory networks and protein-protein interaction networks simultaneously from DNA microarray data, protein-protein interaction data and other genome-wide data. RESULTS: We unify Bayesian networks and Markov networks for estimating gene regulatory networks and protein-protein interaction networks according to the reliability of each biological information source. Through the simultaneous construction of gene regulatory networks and protein-protein interaction networks of Saccharomyces cerevisiae cell cycle, we predict the role of several genes whose functions are currently unknown. By using our probabilistic model, we can detect false positives of high-throughput data, such as yeast two-hybrid data. In a genome-wide experiment, we find possible gene regulatory relationships and protein-protein interactions between large protein complexes that underlie complex regulatory mechanisms of biological processes.     

Using indirect protein-protein interactions for protein complex prediction

Protein complexes are fundamental for understanding principles of cellular organizations. As the sizes of protein-protein interaction (PPI) networks are increasing, accurate and fast protein complex prediction from these PPI networks can serve as a guide for biological experiments to discover novel protein complexes. However, it is not easy to predict protein complexes from PPI networks, especially in situations where the PPI network is noisy and still incomplete. Here, we study the use of indirect interactions between level-2 neighbors (level-2 interactions) for protein complex prediction. We know from previous work that proteins which do not interact but share interaction partners (level-2 neighbors) often share biological functions. We have proposed a method in which all direct and indirect interactions are first weighted using topological weight (FS-Weight), which estimates the strength of functional association. Interactions with low weight are removed from the network, while level-2 interactions with high weight are introduced into the interaction network. Existing clustering algorithms can then be applied to this modified network. We have also proposed a novel algorithm that searches for cliques in the modified network, and merge cliques to form clusters using a "partial clique merging" method. Experiments show that (1) the use of indirect interactions and topological weight to augment protein-protein interactions can be used to improve the precision of clusters predicted by various existing clustering algorithms; and (2) our complex-finding algorithm performs very well on interaction networks modified in this way. Since no other information except the original PPI network is used, our approach would be very useful for protein complex prediction, especially for prediction of novel protein complexes.     

Multicolor bimolecular fluorescence complementation reveals simultaneous formation of alternative CBL/CIPK complexes in planta

The specificity of intracellular signaling and developmental patterning in biological systems relies on selective interactions between different proteins in specific cellular compartments. The identification of such protein-protein interactions is essential for unraveling complex signaling and regulatory networks. Recently, bimolecular fluorescence complementation (BiFC) has emerged as a powerful technique for the efficient detection of protein interactions in their native subcellular localization. Here we report significant technical advances in the methodology of plant BiFC. We describe a series of versatile BiFC vector sets that are fully compatible with previously generated vectors. The new vectors enable the generation of both C-terminal and N-terminal fusion proteins and carry optimized fluorescent protein genes that considerably improve the sensitivity of BiFC. Using these vectors, we describe a multicolor BiFC (mcBiFC) approach for the simultaneous visualization of multiple protein interactions in the same cell. Application to a protein interaction network acting in calcium-mediated signal transduction revealed the concurrent interaction of the protein kinase CIPK24 with the calcium sensors CBL1 and CBL10 at the plasma membrane and tonoplast, respectively. We have also visualized by mcBiFC the simultaneous formation of CBL1/CIPK1 and CBL9/CIPK1 protein complexes at the plasma membrane. Thus, mcBiFC provides a useful new tool for exploring complex regulatory networks in plants.     

Exploration of the Dynamic Properties of Protein Complexes Predicted from Spatially Constrained Protein-Protein Interaction Networks

Protein complexes are not static, but rather highly dynamic with subunits that undergo 1-dimensional diffusion with respect to each other. Interactions within protein complexes are modulated through regulatory inputs that alter interactions and introduce new components and deplete existing components through exchange. While it is clear that the structure and function of any given protein complex is coupled to its dynamical properties, it remains a challenge to predict the possible conformations that complexes can adopt. Protein-fragment Complementation Assays detect physical interactions between protein pairs constrained to ≤8 nm from each other in living cells. This method has been used to build networks composed of 1000s of pair-wise interactions. Significantly, these networks contain a wealth of dynamic information, as the assay is fully reversible and the proteins are expressed in their natural context. In this study, we describe a method that extracts this valuable information in the form of predicted conformations, allowing the user to explore the conformational landscape, to search for structures that correlate with an activity state, and estimate the abundance of conformations in the living cell. The generator is based on a Markov Chain Monte Carlo simulation that uses the interaction dataset as input and is constrained by the physical resolution of the assay. We applied this method to an 18-member protein complex composed of the seven core proteins of the budding yeast Arp2/3 complex and 11 associated regulators and effector proteins. We generated 20,480 output structures and identified conformational states using principle component analysis. We interrogated the conformation landscape and found evidence of symmetry breaking, a mixture of likely active and inactive conformational states and dynamic exchange of the core protein Arc15 between core and regulatory components. Our method provides a novel tool for prediction and visualization of the hidden dynamics within protein interaction networks.     

Architecture of basic building blocks in protein and domain structural interaction networks

MOTIVATION: The structural interaction of proteins and their domains in networks is one of the most basic molecular mechanisms for biological cells. Topological analysis of such networks can provide an understanding of and solutions for predicting properties of proteins and their evolution in terms of domains. A single paradigm for the analysis of interactions at different layers, such as domain and protein layers, is needed. RESULTS: Applying a colored vertex graph model, we integrated two basic interaction layers under a unified model: (1) structural domains and (2) their protein/complex networks. We identified four basic and distinct elements in the model that explains protein interactions at the domain level. We searched for motifs in the networks to detect their topological characteristics using a pruning strategy and a hash table for rapid detection. We obtained the following results: first, compared with a random distribution, a substantial part of the protein interactions could be explained by domain-level structural interaction information. Second, there were distinct kinds of protein interaction patterns classified by specific and distinguishable numbers of domains. The intermolecular domain interaction was the most dominant protein interaction pattern. Third, despite the coverage of the protein interaction information differing among species, the similarity of their networks indicated shared architectures of protein interaction network in living organisms. Remarkably, there were only a few basic architectures in the model (>10 for a 4-node network topology), and we propose that most biological combinations of domains into proteins and complexes can be explained by a small number of key topological motifs. CONTACT: doheon@kaist.ac.kr.     

Exploring overlapping functional units with various structure in protein interaction networks

Revealing functional units in protein-protein interaction (PPI) networks are important for understanding cellular functional organization. Current algorithms for identifying functional units mainly focus on cohesive protein complexes which have more internal interactions than external interactions. Most of these approaches do not handle overlaps among complexes since they usually allow a protein to belong to only one complex. Moreover, recent studies have shown that other non-cohesive structural functional units beyond complexes also exist in PPI networks. Thus previous algorithms that just focus on non-overlapping cohesive complexes are not able to present the biological reality fully. Here, we develop a new regularized sparse random graph model (RSRGM) to explore overlapping and various structural functional units in PPI networks. RSRGM is principally dominated by two model parameters. One is used to define the functional units as groups of proteins that have similar patterns of connections to others, which allows RSRGM to detect non-cohesive structural functional units. The other one is used to represent the degree of proteins belonging to the units, which supports a protein belonging to more than one revealed unit. We also propose a regularizer to control the smoothness between the estimators of these two parameters. Experimental results on four S. cerevisiae PPI networks show that the performance of RSRGM on detecting cohesive complexes and overlapping complexes is superior to that of previous competing algorithms. Moreover, RSRGM has the ability to discover biological significant functional units besides complexes.     

In search of the biological significance of modular structures in protein networks

Many complex networks such as computer and social networks exhibit modular structures, where links between nodes are much denser within modules than between modules. It is widely believed that cellular networks are also modular, reflecting the relative independence and coherence of different functional units in a cell. While many authors have claimed that observations from the yeast protein–protein interaction (PPI) network support the above hypothesis, the observed structural modularity may be an artifact because the current PPI data include interactions inferred from protein complexes through approaches that create modules (e.g., assigning pairwise interactions among all proteins in a complex). Here we analyze the yeast PPI network including protein complexes (PIC network) and excluding complexes (PEC network). We find that both PIC and PEC networks show a significantly greater structural modularity than that of randomly rewired networks. Nonetheless, there is little evidence that the structural modules correspond to functional units, particularly in the PEC network. More disturbingly, there is no evolutionary conservation among yeast, fly, and nematode modules at either the whole-module or protein-pair level. Neither is there a correlation between the evolutionary or phylogenetic conservation of a protein and the extent of its participation in various modules. Using computer simulation, we demonstrate that a higher-than-expected modularity can arise during network growth through a simple model of gene duplication, without natural selection for modularity. Taken together, our results suggest the intriguing possibility that the structural modules in the PPI network originated as an evolutionary byproduct without biological significance.     

Progress in the identification of interaction sites on the periplasmic maltose binding protein from E coli

The periplasmic maltose binding protein (MBP) is required for the high affinity transport of maltose and maltodextrins and for chemotaxis towards these sugars. In these functions, MBP interacts with proteins of the cytoplasmic membrane: MalF and MalG for transport, Tar for chemotaxis. A large number of MBP mutations have been isolated by us and other laboratories. We grouped these mutations into classes depending on the interactions affected and we represented the corresponding residues on the 3-D model for MBP so as to further identify the sites of MBP interacting with the MalF-MalG complex and with the Tar protein. MBP (like the other binding proteins) is composed of 2 lobes enclosing a cleft where the substrate binds. The face of the protein opposite the cleft seems to interact neither with MalF-MalG nor with Tar. The other face, corresponding to the cleft, contains sites for interactions with MalF-MalG and Tar. These sites appear to cover both sides of the cleft and may overlap in part. The present definition of the interaction sites suggests further that MBP has different in vivo orientations when it interacts with MalF-MalG or with Tar. This work constitutes an additional step in combining the use of genetic and structural analysis to define the interaction sites on MBP. Because of the structural similarities between periplasmic binding proteins, the regions of interaction defined could be relevant for other members of this family.     

Identification of conserved protein complexes based on a model of protein network evolution

MOTIVATION: Data on protein-protein interactions (PPIs) are increasing exponentially. To date, large-scale protein interaction networks are available for human and most model species. The arising challenge is to organize these networks into models of cellular machinery. As in other biological domains, a comparative approach provides a powerful basis for addressing this challenge. RESULTS: We develop a probabilistic model for protein complexes that are conserved across two species. The model describes the evolution of conserved protein complexes from an ancestral species by protein interaction attachment and detachment and gene duplication events. We apply our model to search for conserved protein complexes within the PPI networks of yeast and fly, which are the largest networks in public databases. We detect 150 conserved complexes that match well-known complexes in yeast and are coherent in their functional annotations both in yeast and in fly. In comparison with two previous approaches, our model yields higher specificity and sensitivity levels in protein complex detection. AVAILABILITY: The program is available upon request.     

One-step, non-denaturing isolation of an RNA polymerase enzyme complex using an improved multi-use affinity probe resin

The rapid isolation of protein complexes is critical to the goal of establishing protein interaction networks. High-throughput methods for identifying protein binding partners in a way suitable for mass spectrometric identification and structural analysis are required and small molecule/peptide interactions provide the key. We have now shown that a redesigned resin derivatized with a bisarsenical dye can be used to isolate the Shewanella oneidensis RNA polymerase core enzyme with a tetracysteine-tagged RNA polymerase A as bait protein. A critical advantage of this method is the ability to release the intact complex using a mild, one-step procedure with a competing dithiol. In addition to the identification of the core complex, additional interaction partners, including universal stress protein, were identified. These results provide a path forward to identifying how changes in critical protein complexes over time modulate cell function.     

Target selection for complex structural genomics

Most cellular processes are carried out by macromolecular assemblies and regulated through a complex network of transient protein-protein interactions. Genome-wide interaction discovery experiments are already delivering the first drafts of whole organism interactomes and, thus, depicting the limits of the interaction space. However, a complete understanding of molecular interactions can only come from high-resolution three-dimensional structures, as they provide key atomic details about the binding interfaces. The launch of structural genomics initiatives focused on protein interactions and complexes could quickly fill up the interaction space with structural details, offering a new perspective on how cell networks operate at atomic level. Clear target selection strategies that rationally identify the key interactions and complexes that should be first tackled are fundamental to maximize the return, minimize the costs and prevent experimental difficulties.     

A graph theoretical approach for assessing bio-macromolecular complex structural stability

Fast and proper assessment of bio macro-molecular complex structural rigidity as a measure of structural stability can be useful in systematic studies to predict molecular function, and can also enable the design of rapid scoring functions to rank automatically generated bio-molecular complexes. Based on the graph theoretical approach of Jacobs et al. [Jacobs DJ, Rader AJ, Kuhn LA, Thorpe MF (2001) Protein flexibility predictions using graph theory. Proteins: Struct Funct Genet 44:150–165] for expressing molecular flexibility, we propose a new scheme to analyze the structural stability of bio-molecular complexes. This analysis is performed in terms of the identification in interacting subunits of clusters of flappy amino acids (those constituting regions of potential internal motion) that undergo an increase in rigidity at complex formation. Gains in structural rigidity of the interacting subunits upon bio-molecular complex formation can be evaluated by expansion of the network of intra-molecular inter-atomic interactions to include inter-molecular inter-atomic interaction terms. We propose two indices for quantifying this change: one local, which can express localized (at the amino acid level) structural rigidity, the other global to express overall structural stability for the complex. The new system is validated with a series of protein complex structures reported in the protein data bank. Finally, the indices are used as scoring coefficients to rank automatically generated protein complex decoys.     

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.     

Applying bimolecular fluorescence complementation to screen and purify aquaporin protein:protein complexes

Protein:protein interactions play key functional roles in the molecular machinery of the cell. A major challenge for structural biology is to gain high‐resolution structural insight into how membrane protein function is regulated by protein:protein interactions. To this end we present a method to express, detect, and purify stable membrane protein complexes that are suitable for further structural characterization. Our approach utilizes bimolecular fluorescence complementation (BiFC), whereby each protein of an interaction pair is fused to nonfluorescent fragments of yellow fluorescent protein (YFP) that combine and mature as the complex is formed. YFP thus facilitates the visualization of protein:protein interactions in vivo, stabilizes the assembled complex, and provides a fluorescent marker during purification. This technique is validated by observing the formation of stable homotetramers of human aquaporin 0 (AQP0). The method's broader applicability is demonstrated by visualizing the interactions of AQP0 and human aquaporin 1 (AQP1) with the cytoplasmic regulatory protein calmodulin (CaM). The dependence of the AQP0‐CaM complex on the AQP0 C‐terminus is also demonstrated since the C‐terminal truncated construct provides a negative control. This screening approach may therefore facilitate the production and purification of membrane protein:protein complexes for later structural studies by X‐ray crystallography or single particle electron microscopy.     

Interactions of free and immobilized myelin basic protein with anionic detergents

The interaction of free and immobilized myelin basic protein (MBP) with sodium deoxycholate (DOC) and sodium dodecyl sulfate (NaDodSO4) was studied under a variety of conditions. Free MBP formed insoluble complexes with both detergents. Analysis of the insoluble complexes revealed that the molar ratio of detergent/MBP in the precipitate increased in a systematic fashion with increasing detergent concentration until the complex became soluble. At pH 4.8, equilibrium dialysis studies indicated that approximately 15 mol of NaDodSO4 could bind to the protein without precipitation occurring. Regardless of the surfactant, however, minimum protein solubility occurred when the net charge on the protein-detergent complex was between +18 and -9. Complete equilibrium binding isotherms of both detergents to the protein were obtained by using MBP immobilized on agarose. The bulk of the binding of both detergents was highly cooperative and occurred at or above the critical micelle concentration. At I = 0.1, saturation levels of 2.09 +/- 0.15 g of NaDodSO4/g of protein and 1.03 /+- 0.40 g of DOC/g of protein were obtained. Below pH 7.0 the NaDodSO4 binding isotherms revealed an additional cooperative transition corresponding to the binding of 15-20 mol of NaDodSO4/mol of protein. Affinity chromatography studies indicated that, in the presence of NaDodSO4 (but not in its absence), [125I]MBP interacted with agarose-immobilized histone, lysozyme, and MBP but did not interact with ovalbumin-agarose. These data support a model in which the detergent cross-links and causes precipitation of MBP-anionic detergent complexes. Cross-linking may occur through hydrophobic interaction between detergents electrostatically bound to different MBP molecules.     

Protein complex prediction based on maximum matching with domain–domain interaction

With the development of high-throughput methods for identifying protein–protein interactions, large scale interaction networks are available. Computational methods to analyze the networks to detect functional modules as protein complexes are becoming more important. However, most of the existing methods only make use of the protein–protein interaction networks without considering the structural limitations of proteins to bind together. In this paper, we design a new protein complex prediction method by extending the idea of using domain–domain interaction information. Here we formulate the problem into a maximum matching problem (which can be solved in polynomial time) instead of the binary integer linear programming approach (which can be NP-hard in the worst case). We also add a step to predict domain–domain interactions which first searches the database Pfam using the hidden Markov model and then predicts the domain–domain interactions based on the database DOMINE and InterDom which contain confirmed DDIs. By adding the domain–domain interaction prediction step, we have more edges in the DDI graph and the recall value is increased significantly (at least doubled) comparing with the method of Ozawa et al. (2010) [1] while the average precision value is slightly better. We also combine our method with three other existing methods, such as COACH, MCL and MCODE. Experiments show that the precision of the combined method is improved. This article is part of a Special Issue entitled: Computational Methods for Protein Interaction and Structural Prediction.