Fundamentals of protein interaction network mapping

The yeast two hybrid (Y2H)

Membrane yeast two hybrid (MYTH)

Luminescence‐based mammalian interactome mapping (LUMIER)

Mammalian protein–protein interaction trap (MAPPIT)

Kinase substrate sensor (KISS)

Bimolecular fluorescence complementation (BiFC)

Mammalian membrane two hybrid (MaMTH)

Fluorescence resonance energy transfer (FRET)

Bioluminescence resonance energy transfer (BRET)

Affinity purification–mass spectrometry (AP‐MS)

Proximity‐dependent biotin identification coupled to mass spectrometry (BioID‐MS)

Proximity ligation assay (PLA)

Ligand–receptor capture – trifunctional chemoproteomics reagents (LRC‐TriCEPS)

Avidity‐based extracellular interaction screen (AVEXIS)

Assessing PPI datasets

Assessing the frequency of false positives and false negatives in PPI datasets has been a long‐standing problem, especially for HT screens. Typically, the frequency of false positives is measured as the false discovery rate ($FDR=\frac{falsepositives}{truepositives+falsepositives}),$ and the frequency of false negatives as the false negative rate ($FNR=\frac{falsenegatives}{truepositives+falsenegatives}$) or sensitivity ($\frac{truepositives}{truepositives+falsenegatives}$). The main strategies for assessing FDR and sensitivity have involved testing detected interactions by multiple methods and comparing against interactions from literature. FDR has been, arguably, a greater focus in interactome studies than sensitivity. In small‐scale screens, FDR can be assessed and minimized by testing all reported interactions using multiple methods. However, the FDR of small‐scale screens may still be uncertain. Edwards et al (2002) found that interactions from small‐scale screens were not always consistent with known 3D structures of protein complexes. Rolland et al (2014) tested interactions reported in single publications and found that the detection rate was just slightly higher than for random protein pairs. Small‐scale studies rarely report protein pairs that were tested but not detected. Consequently, the sensitivity of their screens and the assessment of how much of the interactome they have tested are largely unknown (Cusick et al, 2009).

Assessing HT screens is more difficult since testing all detected interactions by multiple methods is not feasible. Venkatesan et al (2009) developed a rigorous framework for assessing the quality of HT PPI datasets. Their framework calculates four parameters: screening completeness, assay sensitivity, sampling sensitivity, and precision. Screening completeness is the fraction of open reading frame (ORF) pairs tested in the screen. Assay sensitivity is the fraction of interactions that can be identified by the assay, estimated by testing the assay on a gold standard set of interactions, and determining the fraction detected. Sampling sensitivity is the fraction of detectable interactions identified in one trial of the assay, estimated by repeating the assay multiple times and fitting a Bayesian model to the results. Precision, the fraction of detected pairs that are true positives, can be estimated by testing the assay on reference sets of interacting and non‐interacting protein pairs, and calculating the fraction of detected pairs that are from the interacting set.

Once the precision and sensitivity of an assay have been estimated, the assay can be used to determine the FDR of interaction datasets. HT studies commonly estimate FDR by retesting a subset of detected protein pairs using different small‐scale or HT methods (Yu et al, 2008; Simonis et al, 2009; Rolland et al, 2014). Such estimates need to take into account the precision and sensitivity of the retesting assay. This is especially important as the precision or sensitivity may be quite limited. Braun et al (2009) assessed five HT assays on a gold standard dataset comprised of interactions reported by multiple small‐scale studies (positive cases) and an equal number of randomly chosen protein pairs. Each HT assay detected only ~20–35% of positive cases, and up to 4% of negative cases. Combined, the five assays detected 59% of positive cases, while FDR increased to 14%. Furthermore, different assays have different systematic biases; for example, affinity purification methods may be biased in favor of high‐abundance proteins (Ivanic et al, 2009). Another concern, especially difficult to address, is that gold standard datasets may also have biases. Such datasets, often comprising PPIs reported by multiple small‐scale studies, may be deficient for certain types of proteins or PPIs due to research bias or limitations of assays (Hakes et al, 2008; Edwards et al, 2011; Rolland et al, 2014; Kotlyar et al, 2015; Wang et al, 2015).

Computational methods for assessing results

Computational methods provide a means of estimating FDR without retesting detected protein pairs. Furthermore, they can provide error estimates for specific proteins or protein pairs.

D'haeseleer and Church (2004) introduced a method for estimating FDR and assessing the reliability of individual interactions. Their method analyzes the overlap of detected interactions with two other datasets, including a trusted reference set. The variance of FDR estimates can be high if the overlaps are small. However, the authors showed that FDR estimates are not greatly affected by the quality of the chosen datasets.

A statistical model introduced by Huang and Bader for assessing two‐hybrid datasets provides global error estimates as well as error estimates for specific baits (Huang & Bader, 2009). Thus, it can determine whether certain baits are responsible for a disproportionate share of the global error rate. For example, in two‐hybrid data from worm, it found that the FDR was especially high among proteins involved in cellular metabolic processes.

Computational methods to help improve data quality

One approach for assessing and improving data quality is to examine whether a PPI dataset possesses properties of interacting protein pairs. Methods that use this approach assume that interacting proteins are likely to have co‐expressed genes (Deane et al, 2002), shared subcellular localization (Sprinzak et al, 2003), similar functional and process annotations (Sprinzak et al, 2003; Wang et al, 2007), and shared interaction partners (Saito et al, 2002; Goldberg & Roth, 2003). Evaluating a PPI dataset using such evidence can be problematic: Many interacting protein pairs do not have correlated gene expression, protein annotations such as subcellular localization and function are often incomplete or unavailable, and shared interaction partners are frequently unknown, since the interactomes of most species are largely unmapped. However, ranking detected protein pairs using these types of evidence can help identify true positive interactions. A combination of such evidence has been used in HT studies to define high‐confidence (HC) subsets of detected interactions (Miller et al, 2005; Havugimana et al, 2012). The evidence can also help identify potential false negatives—protein pairs that are not strongly supported by the experimental detection method but have properties of true interactions. Unfortunately, ranking based on this evidence can introduce biases; ranking by correlation of gene expression profiles favors stable interactions (Brown & Jurisica, 2007), while ranking by shared Gene Ontology terms or interaction partners favors well‐studied proteins. If the evidence is used multiple times during the planning and analysis of an experiment, there may be a danger of circular reasoning. For example, testing protein pairs with similar functions and then ranking detected pairs by similarity of localizations would be largely ineffective, as functional similarity is correlated with localization similarity.

An approach for improving the quality of AP‐MS data involves calculating a score for each co‐purified pair, indicating the likelihood of the two proteins being observed together. Such scores have been calculated using various methods: log‐ratios of observed versus expected co‐occurrences (Gavin et al, 2006), machine‐learning algorithms (Krogan et al, 2006; Collins et al, 2007), hypergeometric probabilities (Hart et al, 2007), and randomizations (Yu et al, 2009). Scores can be used for ranking protein pairs and defining a HC subset of interactions. A score threshold for defining this subset can be determined based on FDR and sensitivity calculated from a gold standard dataset comprising interacting and non‐interacting protein pairs. True positive interactions can be distinguished from contaminants by analyzing quantitative information from mass spectrometry data, including spectral counts, signal intensity in the precursor scan of the mass spectrometer, and intensity of product ions after fragmentation (Gingras & Raught, 2012). Analysis of quantitative data using tools such as SAINT (Choi et al, 2011) can be especially helpful when aiming to detect transient interactions; preservation of transient interactions in AP‐MS experiments requires short incubation times and few washes, resulting in more contaminants that need to be filtered (Gingras & Raught, 2012).

Varjosalo et al (2013) filtered AP‐MS data in three steps to remove different types of protein contamination. The first filter removed proteins that may have been left over from a proceeding experiment. The second filter removed non‐specifically interacting proteins. The third filter removed low‐abundance, non‐systematic contaminants; bait–prey pairs were assigned weighted spectral‐count‐based scores reflecting interaction abundance and reproducibility, and pairs with scores below a threshold were removed. This three‐step filtering improved reproducibility of resulting networks more than previous filtering methods, wD‐score (Behrends et al, 2010) and SAINT (Choi et al, 2011).

Computational prediction to help improve datasets and the interactome

Computational PPI prediction is similar to previously described methods that assign scores to detected protein pairs, indicating the likelihood of interaction. However, prediction methods provide scores for both detected and undetected PPIs. These scores can be used to improve the quality of experimentally detected PPIs, by identifying high‐confidence subsets and potential false negatives, which can help accelerate interactome mapping (Schwartz et al, 2009). Also, prediction methods can help fill the gaps in a known interactome by predicting interactions for interactome orphans and low‐degree proteins (Kotlyar et al, 2015).

PPI prediction methods can be categorized by the data they use: genomic data, protein sequence, protein structure, PPI networks, gene expression, and annotations of gene function, localization, and process. Prediction methods based on genomic data analyze conserved operon structure, fusion domains, phylogenetic profiles, and interologs. Analysis of operon structure is based on the idea that genes in close proximity on the genome are more likely to encode interacting proteins, especially if the proximal locations are conserved across species (Dandekar et al, 1998; Overbeek et al, 1999). Similarly, if two genes exist as a single fused gene in another species, they are likely to encode interacting proteins (Enright et al, 1999). Phylogenetic profiles are used to identify gene pairs that tend to co‐occur across species—either both are present in a species, or both are absent; such pairs are likely to be functionally related and may encode interacting proteins (Pellegrini et al, 1999). Interologs are interactions conserved across species: if a pair of proteins interacts in one species, their orthologs in another species are more likely to interact (Walhout et al, 2000; Yu et al, 2004).

Many studies have predicted interactions based on protein sequence (Gomez et al, 2003; Martin et al, 2005; Nanni & Lumini, 2006; Shen et al, 2007; Guo et al, 2008; Zaki et al, 2009; Chang et al, 2010; Guo et al, 2010; Yu et al, 2010). These studies analyze experimentally determined interactions to find patterns that distinguish sequences of an interacting protein pair from those of a non‐interacting pair. This is often done using machine‐learning algorithms such as support vector machines, random forests (Roy et al, 2009), and K‐local hyperplane nearest‐neighbors (Nanni & Lumini, 2006). Protein sequence can also be used indirectly for prediction; protein domains can be determined from sequence, and pairs of domains enriched among known interacting protein pairs may predict new interactions (Sprinzak & Margalit, 2001; Wojcik & Schächter, 2001; Nguyen & Ho, 2006; Singhal & Resat, 2007). Another approach combines sequence with protein tertiary structure. Although few proteins or complexes have known 3D structure, sequence homology can serve as a link to other proteins. Homologous proteins, especially with conserved binding sites, are likely to interact in similar ways (Aloy & Russell, 2003; Ma et al, 2003; Sinha et al, 2010). Thus, a protein pair can be predicted to interact based on sequence or structural homology to proteins in solved complexes (Lu et al, 2002; Aloy & Russell, 2003; Zhang et al, 2012a).

If an interactome is partially known, new interactions may be predicted from known network structure, often based on the idea that interacting proteins tend to share interaction partners (Saito et al, 2002; Goldberg & Roth, 2003; Liu et al, 2008). Other types of interaction evidence—including correlated gene expression, shared subcellular localization, similar function and process—are typically used in combination with other evidence (Jansen et al, 2003; Ben‐Hur & Noble, 2005; Rhodes et al, 2005; Elefsinioti et al, 2011).

PPI prediction methods have a number of limitations and biases, often similar to those of experimental PPI assays. Computational methods tend to have difficulty predicting transient interactions and interactions involving lesser studied proteins, which typically have no tertiary structure data, no detailed Gene Ontology or domain annotations, few known interactions, and few orthologs in different species (Kotlyar et al, 2015). Transient interactions are difficult to predict based on correlation of gene expression profiles (Brown & Jurisica, 2007), or analysis of protein sequence or structure. In these interactions, the two encoding genes are not highly correlated (Brown & Jurisica, 2007), interaction interface sequences are not as conserved as in obligate interactions (Perkins et al, 2010), interacting proteins often undergo conformational changes (Perkins et al, 2010), and interactions are frequently mediated by linear motifs rather than globular domains (Perkins et al, 2010). If proteins lack Gene Ontology annotations, known interaction partners, or orthologs, it is difficult to predict their interactions using annotation similarity, network topology, or comparative genomics, respectively. Interestingly, such proteins are also underrepresented in the experimentally detected human interactome (Kotlyar et al, 2015). If prediction methods require training, they may acquire the biases of their experimentally detected training set. This may explain the finding of Rolland et al that a proteome‐wide, structure‐focused prediction method, PrePPI (Zhang et al, 2012a), had a tendency to report interactions among well‐studied proteins (Rolland et al, 2014).

Visualization Tools

A number of tools are available for visualization and analysis of PPI data including Cytoscape (Su et al, 2014), NAViGaTOR (Brown et al, 2009), and packages from R and Bioconductor (e.g., Rintact (Chiang et al, 2008) combined with RBGL). The main types of functionality supported by these tools include loading PSI‐MI files, visualizing networks, annotating networks, and conducting network analysis. Data can be loaded from tab‐delimited or PSI‐MI XML files, and visualized as a graph, with nodes representing proteins and edges representing interactions. Multiple graph layouts are supported, including grids and force‐directed layouts. Annotations for nodes and edges can be included in the original data files, retrieved from other text files, or imported from databases. The appearance of nodes and edges can be set based on annotations. Network analysis capabilities include clustering to identify protein complexes, motifs, or graphlets, calculating centrality measures, and identifying shortest paths or flows.

Identifying complexes in PPI networks

Although PPI networks focus on pairwise interactions, cellular processes are often carried out by protein complexes. Complexes typically have a “core”—a central functional unit present in most isoforms of the complex, and “attachments”—proteins present in some isoforms of the complex (Gavin et al, 2006). The attachments may include “modules”—sets of proteins that always appear together in different complexes (Gavin et al, 2006).

Experimental methods for detecting PPIs cannot easily identify complexes. For example, Y2H methods only identify binary interactions, and while TAP and HMS‐PCI identify potential complexes, reliably identifying complex members requires “reverse purification”—repeatedly applying the detection method, using candidate members of the complex as baits (Gavin et al, 2002).

Computational methods can predict complexes by analyzing PPI networks and integrating networks with information such as gene function or co‐expression. Most complex prediction methods share the same main steps: (i) assigning confidence scores to detected interactions, (ii) identifying complexes by clustering PPI networks or analyzing additional data, and (iii) evaluating resulting complexes by comparing with gold standard datasets. The first step assigns confidence scores to detected interactions; scores can be used to filter interactions or can be included as input to clustering algorithms. Any of the scoring approaches described earlier may be used (see section “Computational methods to help improve data quality”). Often, complexes are determined from AP‐MS data, and scoring approaches specific to this data are used.

Most prediction methods assume that complexes correspond to highly connected regions of PPI networks and cluster the networks to identify these regions. The clustering approaches can be categorized as agglomerative or divisive, and overlapping or non‐overlapping. Agglomerative approaches (Bader & Hogue, 2003; Li et al, 2005; Liu et al, 2009; Wang et al, 2009; Nepusz et al, 2012) start with seeds—individual nodes or cliques—and expand them into larger clusters by adding single nodes or merging with other clusters. Divisive approaches (van Dongen, 2000; Pu et al, 2007; Friedel et al, 2009) start with an entire network and partition it into highly connected regions. Overlapping approaches (Wang et al, 2009; Nepusz et al, 2012) allow nodes to be members of multiple clusters, to reflect overlap between complexes, while non‐overlapping approaches (van Dongen, 2000; Bader & Hogue, 2003; Liu et al, 2009) assign nodes to single clusters. Some methods (Wu et al, 2009; Leung et al, 2009; Srihari et al, 2010; Chin et al, 2010) try to identify core and attachment sections of complexes.

Several methods combine network clustering with information about protein function, orthology, or structure. To increase the reliability of predicted complexes, these methods look for clusters whose members have similar functions (King et al, 2004; Li et al, 2007), highly conserved orthologs in the same set of species (i.e., the complex is conserved as a functional unit (Sharan et al, 2005; Hirsh & Sharan, 2007)), and protein structures enabling simultaneous interactions with multiple complex members (Ozawa et al, 2010; Jung et al, 2010). Several surveys (Brohée & van Helden, 2006; Vlasblom & Wodak, 2009; Li et al, 2010; Srihari & Leong, 2013) evaluated complex prediction methods by comparing their results against experimentally determined complexes. The Markov Cluster Algorithm (van Dongen, 2000; van Dongen & Abreu‐Goodger, 2012) was found to be a top clustering method in three surveys (Brohée & van Helden, 2006; Vlasblom & Wodak, 2009; Li et al, 2010), and integration of network clustering with other information significantly improved performance (Srihari & Leong, 2013).

Identifying interaction conditions

Understanding how PPIs produce specific phenotypes requires information on their context: when, where, and under what conditions interactions occur. Computational methods can help determine this information by text mining of the PubMed database (Chowdhary et al, 2012), or more commonly, by integrating transcriptomic and other data with PPI networks. Usually, these methods aim to identify cell types, tissues, and disease states in which interactions occur.

Direct evidence for interactions occurring in a given cell type or tissue is often unavailable since PPI detection is typically done in yeast cells or common cell lines. By contrast, HT gene expression data are available for a wide variety of organisms, cell types, tissues, and conditions (Barrett et al, 2013; Kolesnikov et al, 2015). A common approach for assigning PPIs to tissues is to check whether the genes encoding an interacting protein pair are both expressed in a tissue (Bossi & Lehner, 2009; Lopes et al, 2011). Proteomics data (Uhlen et al, 2015) are less extensive but can be used analogously. The TissueNet (Barshir et al, 2013) database uses both gene and protein expression data to assign PPIs to tissues. Assigning tissues on the basis of gene or protein expression has limitations; absence of gene expression may not indicate absence of protein expression, and presence of gene or protein expression may not mean that proteins interact. Also, since this approach estimates the presence or absence of proteins, it can only indicate whether all interactions involving a protein are absent, but not whether a specific interaction is absent. Correlation of gene expression profiles can provide information on specific interactions; a pair of genes with correlated expression profiles in a tissue or cell type may have interacting protein products (Camargo & Azuaje, 2007).

Interactions that change in disease or other conditions can be identified by similar approaches. An interaction may be disease‐related if the two encoding genes are both expressed only in the disease state (or are upregulated in the disease state; Ideker et al, 2002), or the genes have correlated expression profiles in disease states (Camargo & Azuaje, 2007; Guo et al, 2007; Xiao et al, 2012). Differential correlation of gene expression profiles can provide more specific information about an interaction: if two genes have significantly different correlation levels in two conditions, then the interaction of their protein products may change between conditions (Lin et al, 2010; Yoon et al, 2011; Zhang et al, 2012b; Yu et al, 2013).

Integrating PPI networks with other omics data

Integrating PPI networks with other omics data, such as genomic, transcriptomic, and proteomic, is essential for understanding the molecular basis of phenotypes. Just as gene expression data can provide context for PPIs, and link them with specific conditions, PPI networks can provide context for other data, and link it with phenotype.

One of the most common types of integration combines PPI networks and gene‐phenotype data, to uncover relationships between genes and diseases. Goh et al (2007) showed that essential genes and disease genes have distinct network properties: essential genes tend to encode hub proteins, while disease genes encode proteins in the periphery of the network. Genes implicated in similar diseases tend to encode proteins that are close in PPI networks—either interacting directly (Goh et al, 2007; Schadt, 2009) or members of the same complex (Lage et al, 2007), pathway (Wood et al, 2007), or subnetwork (Lim et al, 2006). Based on this idea, it is possible to identify novel disease genes by mapping known disease‐associated genes to nodes in PPI networks, and applying random walk (Kohler et al, 2008; Smedley et al, 2014), network flow (Yeger‐Lotem et al, 2009; Chen et al, 2011), label propagation (Lee et al, 2011a), or other related algorithms (Vanunu et al, 2010; Winter et al, 2012). Random walk algorithms have been shown to be especially effective (Navlakha & Kingsford, 2010).

Integrating PPI networks with protein–DNA interactions, gene expression, phenotype, and drug information can provide insights into disease and drug mechanisms and can help identify new treatments. PPI networks combined with protein–DNA interactions have been used to model cellular regulatory networks—identifying regulatory circuits (Yeger‐Lotem et al, 2004) and signaling‐regulatory pathways (Ourfali et al, 2007). More recently, networks were used to predict disease mechanisms by modeling pathogen induced perturbations (Gulbahce et al, 2012), and effects of node or edge removal (Zhong et al, 2009; Sahni et al, 2013). Networks have also been effective for developing treatments: identifying drug targets (Yeh et al, 2012; Emig et al, 2013), understanding drug mechanism of action (Perez‐Lopez et al, 2015), predicting side effects (Huang et al, 2013b), predicting drug–drug interactions (Huang et al, 2013a), and characterizing drug‐regulated genes and toxicity (Kotlyar et al, 2012).

Biological validations

Direct experimental validation of the biological relevance of interactions is the final important step in any interactome mapping project. While complete validation of all novel interactions detected is seldom possible within the context of a single study, demonstrating that a particular interactome provides information of practical biological importance can be done by further analysis of a representative subset of interactions.

Selection of the subset of interactions to study is highly situational, and will depend largely on the nature of the proteins being investigated and the information currently available about them, as well as the size of the interactome and the specific goals of the study. For example, if studying the interactions of a protein whose mutation is known to be associated with disease, interactions which differ between the WT and mutant forms of the protein would likely be highly informative candidates for initial validation. Interactions involving members specifically associated with a given process of interest, which have not been previously demonstrated to interact, also represent a good starting point. Integrating the interactome with other datasets, combined with various predictive algorithms (as described above), is valuable in this selection process, and can help identify candidates based on a more complex range of user‐defined criteria.

The specific validation experiments to be performed also vary on a case‐by‐case basis. Typical initial characterization experiments involve disrupting the level of individual members of an interaction pair (e.g., by gene deletion/knockdown or overexpression), and then looking for changes in the properties or function of the other member. For example, if studying the interactions of a particular receptor, one could investigate the effect of altering gene expression levels of identified interactors on downstream signaling cascades controlled by the receptor. Alternatively, effects on protein stability, protein trafficking, posttranslational modification, or responsiveness to known ligands/substrates could be probed. Investigations can be as specific as centering on molecular effects on individual proteins, or more broadly explore general phenotypic change (e.g., increased sensitivity to particular drugs, inability to grow under certain conditions). Mutational analysis of proteins can also be useful in identifying regions important for mediating and regulating interactions. For examples of proteomics screens followed by functional follow‐ups, we refer the reader to several recent studies (Babu et al, 2012; Snider et al, 2013; Petschnigg et al, 2014).

The importance of performing these validations cannot be understated, as they provide a clear demonstration of the usefulness of any newly generated interactome in providing a solid starting point for the identification and characterization of biologically important processes. If an interactome cannot easily provide this information, then it is unlikely to be of widespread value to the scientific community, and further improvements are necessary. It is also critical to note that carrying out proper validations may represent a significant effort, and researchers must take this into account when planning and implementing any interactome mapping project, regardless of scale.