Roles for the two-hybrid system in exploration of the yeast protein interactome

Comprehensive analysis of protein-protein interactions is a challenging endeavor of functional proteomics and has been best explored in the budding yeast. The yeast protein interactome analysis was achieved first by using the yeast two-hybrid system in a proteome-wide scale and next by large-scale mass spectrometric analysis of affinity-purified protein complexes. While these interaction data have led to a number of novel findings and the emergence of a single huge network containing thousands of proteins, they suffer many false signals and fall short of grasping the entire interactome. Thus, continuous efforts are necessary in both bioinformatics and experimentation to fully exploit these data and to proceed another step forward to the goal. Computational tools to integrate existing biological knowledge buried in literature and various functional genomic data with the interactome data are required for biological interpretation of the huge protein interaction network. Novel experimental methods have to be developed to detect weak, transient interactions involving low abundance proteins as well as to obtain clues to the biological role for each interaction. Since the yeast two-hybrid system can be used for the mapping of the interaction domains and the isolation of interaction-defective mutants, it would serve as a technical basis for the latter purpose, thereby playing another important role in the next phase of protein interactome research.     

Protein-protein interaction networks: from interactions to networks

The goal of interaction proteomics that studies the protein-protein interactions of all expressed proteins is to understand biological processes that are strictly regulated by these interactions. The availability of entire genome sequences of many organisms and high-throughput analysis tools has led scientists to study the entire proteome (Pandey and Mann, 2000). There are various high-throughput methods for detecting protein interactions such as yeast two-hybrid approach and mass spectrometry to produce vast amounts of data that can be utilized to decipher protein functions in complicated biological networks. In this review, we discuss recent developments in analytical methods for large-scale protein interactions and the future direction of interaction proteomics.     

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.     

Greedily building protein networks with confidence

MOTIVATION: With genome sequences complete for human and model organisms, it is essential to understand how individual genes and proteins are organized into biological networks. Much of the organization is revealed by proteomics experiments that now generate torrents of data. Extracting relevant complexes and pathways from high-throughput proteomics data sets has posed a challenge, however, and new methods to identify and extract networks are essential. We focus on the problem of building pathways starting from known proteins of interest. RESULTS: We have developed an efficient, greedy algorithm, SEEDY, that extracts biologically relevant biological networks from protein-protein interaction data, building out from selected seed proteins. The algorithm relies on our previous study establishing statistical confidence levels for interactions generated by two-hybrid screens and inferred from mass spectrometric identification of protein complexes. We demonstrate the ability to extract known yeast complexes from high-throughput protein interaction data with a tunable parameter that governs the trade-off between sensitivity and selectivity. DNA damage repair pathways are presented as a detailed example. We highlight the ability to join heterogeneous data sets, in this case protein-protein interactions and genetic interactions, and the appearance of cross-talk between pathways caused by re-use of shared components. SIGNIFICANCE AND COMPARISON: The significance of the SEEDY algorithm is that it is fast, running time O[(E + V) log V] for V proteins and E interactions, a single adjustable parameter controls the size of the pathways that are generated, and an associated P-value indicates the statistical confidence that the pathways are enriched for proteins with a coherent function. Previous approaches have focused on extracting sub-networks by identifying motifs enriched in known biological networks. SEEDY provides the complementary ability to perform a directed search based on proteins of interest. AVAILABILITY: SEEDY software (Perl source), data tables and confidence score models (R source) are freely available from the author.     

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.     

Probabilistic inference of molecular networks from noisy data sources

Information on molecular networks, such as networks of interacting proteins, comes from diverse sources that contain remarkable differences in distribution and quantity of errors. Here, we introduce a probabilistic model useful for predicting protein interactions from heterogeneous data sources. The model describes stochastic generation of protein-protein interaction networks with real-world properties, as well as generation of two heterogeneous sources of protein-interaction information: research results automatically extracted from the literature and yeast two-hybrid experiments. Based on the domain composition of proteins, we use the model to predict protein interactions for pairs of proteins for which no experimental data are available. We further explore the prediction limits, given experimental data that cover only part of the underlying protein networks. This approach can be extended naturally to include other types of biological data sources.     

Proteomic approaches for generating comprehensive protein interaction maps

The availability of complete genome sequences of numerous model organisms has initiated the development of new approaches in biological research to complement conventional biochemistry and genetics. In this context, high-throughput methods for detecting protein interactions, such as mass spectrometry and yeast two-hybrid assays, have produced vast amounts of data that can be exploited to infer protein function and regulation. In this review, we explore different genome-wide protein interaction studies and comment on their extrapolation towards understanding protein functions. It is likely that improvements of these approaches, together with more sophisticated databases and the invention of novel technologies, will help to decipher the complex interactions among proteins and to integrate interacting proteins into existing and novel cellular pathways.     

Towards an understating of signal transduction protein interaction networks

Protein network analysis has witnessed a number of advancements in the past for understanding molecular characteristics for important network topologies in biological systems. The signaling pathway regulates cell cycle progression and anti-apoptotic molecules. This pathway is also involved in maintaining cell survival by modulating the activity of apoptosis through RAS, P13K, AKT and BAD activities. The importance of protein-protein interactions to improve usability of the interactome by scoring and ranking interaction data for proteins in signal transduction networks is illustrated using available data and resources.     

DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions

The Database of Interacting Proteins (DIP: http://dip.doe-mbi.ucla.edu) is a database that documents experimentally determined protein–protein interactions. It provides the scientific community with an integrated set of tools for browsing and extracting information about protein interaction networks. As of September 2001, the DIP catalogs ~11 000 unique interactions among 5900 proteins from >80 organisms; the vast majority from yeast, Helicobacter pylori and human. Tools have been developed that allow users to analyze, visualize and integrate their own experimental data with the information about protein–protein interactions available in the DIP database.     

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.     

POINT: a database for the prediction of protein-protein interactions based on the orthologous interactome

One possible path towards understanding the biological function of a target protein is through the discovery of how it interfaces within protein-protein interaction networks. The goal of this study was to create a virtual protein-protein interaction model using the concepts of orthologous conservation (or interologs) to elucidate the interacting networks of a particular target protein. POINT (the prediction of interactome database) is a functional database for the prediction of the human protein-protein interactome based on available orthologous interactome datasets. POINT integrates several publicly accessible databases, with emphasis placed on the extraction of a large quantity of mouse, fruit fly, worm and yeast protein-protein interactions datasets from the Database of Interacting Proteins (DIP), followed by conversion of them into a predicted human interactome. In addition, protein-protein interactions require both temporal synchronicity and precise spatial proximity. POINT therefore also incorporates correlated mRNA expression clusters obtained from cell cycle microarray databases and subcellular localization from Gene Ontology to further pinpoint the likelihood of biological relevance of each predicted interacting sets of protein partners.     

Predicting active site residue annotations in the Pfam database

Background

The recent increase in the use of high-throughput two-hybrid analysis has generated large quantities of data on protein interactions. Specifically, the availability of information about experimental protein-protein interactions and other protein features on the Internet enables human protein-protein interactions to be computationally predicted from co-evolution events (interolog). This study also considers other protein interaction features, including sub-cellular localization, tissue-specificity, the cell-cycle stage and domain-domain combination. Computational methods need to be developed to integrate these heterogeneous biological data to facilitate the maximum accuracy of the human protein interaction prediction.

Results

This study proposes a relative conservation score by finding maximal quasi-cliques in protein interaction networks, and considering other interaction features to formulate a scoring method. The scoring method can be adopted to discover which protein pairs are the most likely to interact among multiple protein pairs. The predicted human protein-protein interactions associated with confidence scores are derived from six eukaryotic organisms – rat, mouse, fly, worm, thale cress and baker's yeast.

Conclusion

Evaluation results of the proposed method using functional keyword and Gene Ontology (GO) annotations indicate that some confidence is justified in the accuracy of the predicted interactions. Comparisons among existing methods also reveal that the proposed method predicts human protein-protein interactions more accurately than other interolog-based methods.     

Analysis of protein interactions within the cytokinin-signaling pathway of Arabidopsis thaliana

The signal of the plant hormone cytokinin is perceived by membrane-located sensor histidine kinases and transduced by other members of the plant two-component system. In Arabidopsis thaliana, 28 two-component system proteins (phosphotransmitters and response regulators) act downstream of three receptors, transmitting the signal from the membrane to the nucleus and modulating the cellular response. Although the principal signaling mechanism has been elucidated, redundancy in the system has made it difficult to understand which of the many components interact to control the downstream biological processes. Here, we present a large-scale interaction study comprising most members of the Arabidopsis cytokinin signaling pathway. Using the yeast two-hybrid system, we detected 42 new interactions, of which more than 90% were confirmed by in vitro coaffinity purification. There are distinct patterns of interaction between protein families, but only a few interactions between proteins of the same family. An interaction map of this signaling pathway shows the Arabidopsis histidine phosphotransfer proteins as hubs, which interact with members from all other protein families, mostly in a redundant fashion. Domain-mapping experiments revealed the interaction domains of the proteins of this pathway. Analyses of Arabidopsis histidine phosphotransfer protein 5 mutant proteins showed that the presence of the canonical phospho-accepting histidine residue is not required for the interactions. Interaction of A-type response regulators with Arabidopsis histidine phosphotransfer proteins but not with B-type response regulators suggests that their known activity in feedback regulation may be realized by interfering at the level of Arabidopsis histidine phosphotransfer protein-mediated signaling. This study contributes to our understanding of the protein interactions of the cytokinin-signaling system and provides a framework for further functional studies in planta.     

Systematic interpretation of genetic interactions using protein networks

Genetic interaction analysis,in which two mutations have a combined effect not exhibited by either mutation alone, is a powerful and widespread tool for establishing functional linkages between genes. In the yeast Saccharomyces cerevisiae, ongoing screens have generated >4,800 such genetic interaction data. We demonstrate that by combining these data with information on protein-protein, prote in-DNA or metabolic networks, it is possible to uncover physical mechanisms behind many of the observed genetic effects. Using a probabilistic model, we found that 1,922 genetic interactions are significantly associated with either between- or within-pathway explanations encoded in the physical networks, covering approximately 40% of known genetic interactions. These models predict new functions for 343 proteins and suggest that between-pathway explanations are better than within-pathway explanations at interpreting genetic interactions identified in systematic screens. This study provides a road map for how genetic and physical interactions can be integrated to reveal pathway organization and function.     

Discovering pathways by orienting edges in protein interaction networks

Modern experimental technology enables the identification of the sensory proteins that interact with the cells' environment or various pathogens. Expression and knockdown studies can determine the downstream effects of these interactions. However, when attempting to reconstruct the signaling networks and pathways between these sources and targets, one faces a substantial challenge. Although pathways are directed, high-throughput protein interaction data are undirected. In order to utilize the available data, we need methods that can orient protein interaction edges and discover high-confidence pathways that explain the observed experimental outcomes. We formalize the orientation problem in weighted protein interaction graphs as an optimization problem and present three approximation algorithms based on either weighted Boolean satisfiability solvers or probabilistic assignments. We use these algorithms to identify pathways in yeast. Our approach recovers twice as many known signaling cascades as a recent unoriented signaling pathway prediction technique and over 13 times as many as an existing network orientation algorithm. The discovered paths match several known signaling pathways and suggest new mechanisms that are not currently present in signaling databases. For some pathways, including the pheromone signaling pathway and the high-osmolarity glycerol pathway, our method suggests interesting and novel components that extend current annotations.     

Influence of Protein Abundance on High-Throughput Protein-Protein Interaction Detection

Experimental protein-protein interaction (PPI) networks are increasingly being exploited in diverse ways for biological discovery. Accordingly, it is vital to discern their underlying natures by identifying and classifying the various types of deterministic (specific) and probabilistic (nonspecific) interactions detected. To this end, we have analyzed PPI networks determined using a range of high-throughput experimental techniques with the aim of systematically quantifying any biases that arise from the varying cellular abundances of the proteins. We confirm that PPI networks determined using affinity purification methods for yeast and Eschericia coli incorporate a correlation between protein degree, or number of interactions, and cellular abundance. The observed correlations are small but statistically significant and occur in both unprocessed (raw) and processed (high-confidence) data sets. In contrast, the yeast two-hybrid system yields networks that contain no such relationship. While previously commented based on mRNA abundance, our more extensive analysis based on protein abundance confirms a systematic difference between PPI networks determined from the two technologies. We additionally demonstrate that the centrality-lethality rule, which implies that higher-degree proteins are more likely to be essential, may be misleading, as protein abundance measurements identify essential proteins to be more prevalent than nonessential proteins. In fact, we generally find that when there is a degree/abundance correlation, the degree distributions of nonessential and essential proteins are also disparate. Conversely, when there is no degree/abundance correlation, the degree distributions of nonessential and essential proteins are not different. However, we show that essentiality manifests itself as a biological property in all of the yeast PPI networks investigated here via enrichments of interactions between essential proteins. These findings provide valuable insights into the underlying natures of the various high-throughput technologies utilized to detect PPIs and should lead to more effective strategies for the inference and analysis of high-quality PPI data sets.     

Construction of reliable protein-protein interaction networks with a new interaction generality measure

MOTIVATION: Recent screening techniques have made large amounts of protein-protein interaction data available, from which biologically important information such as the function of uncharacterized proteins, the existence of novel protein complexes, and novel signal-transduction pathways can be discovered. However, experimental data on protein interactions contain many false positives, making these discoveries difficult. Therefore computational methods of assessing the reliability of each candidate protein-protein interaction are urgently needed. RESULTS: We developed a new 'interaction generality' measure (IG2) to assess the reliability of protein-protein interactions using only the topological properties of their interaction-network structure. Using yeast protein-protein interaction data, we showed that reliable protein-protein interactions had significantly lower IG2 values than less-reliable interactions, suggesting that IG2 values can be used to evaluate and filter interaction data to enable the construction of reliable protein-protein interaction networks.