Computational Prediction of Protein Complexes from Protein Interaction Networks. Sriganesh Srihari

Table 2.4 Classification of confidence scoring (PPI weighting) schemes for protein interactions

Classification	Scoring Scheme	Reference
Sampling or counting based	Bootstrap sampling	[Friedel et al. 2009]
	Comparative Proteomic Analysis (ComPASS)Dice coefficientaHypergeometric samplingSignificance Analysis of INTeractions (SAINT)Socio-affinity scoring	[Sowa et al. 2009][Zhang et al. 2008][Hart et al. 2007][Choi et al. 2011, Teo et al. 2014][Gavin et al. 2006]
Independent evidence-based	Bayesian networks and C4.5 decision treesTopological Clustering Semantic Similarity (TCSS)Purification Enrichment (PE)	[Krogan et al. 2006][Jain and Bader 2010][Collins et al. 2007]
Topology-based	Collaborative Filtering (CF)Functional Similarity (FS) Weight aGeometric embeddingIterative Czekanowski-Dice(ICD) distance aPageRank affinity	[Luo et al. 2015][Chua et al. 2006][Pržulj et al. 2004, Higham et al. 2008][Liu et al. 2008][Voevodski et al. 2009]

      a. Dice coefficient, FS Weight, and Iterative CD scoring schemes can also be considered as independent evidence-based schemes, because if a pair of proteins have several common partners then these proteins most likely perform the same or similar functions and/or are present in the same cellular compartment (a biological evidence).

       Sampling or Counting-Based Schemes

      These schemes estimate the confidence of protein pairs by measuring the number of times each protein pair is observed to interact across multiple trials against what would be expected by chance given the abundance of each protein in the library. If the protein pairs are coming from the same experiment, the counting is performed across multiple purifications of the experiment. Given multiple PPI datasets, this idea can be extended to score interacting pairs by measuring the number of times each pair is observed across the different datasets against what would be expected from random given the number of times these proteins appear across the datasets. However, if the PPI datasets come from different experiments (e.g., Y2H and TAP/MS-based), which is usually the case, then it is useful to capture the relative reliability of each experimental technique or source of the datasets into this computation. For example, if Y2H is believed to be less reliable than TAP/MS-based techniques, then protein pairs can be assigned lower weights when observed in Y2H datasets, but assigned higher weights when observed in TAP/MS datasets.

      In the study by Gavin et al. [2006], a “socio-affinity” scheme based on this counting idea was used to estimate confidence for interactions inferred from pulled-down complexes detected from TAP purifications. The interactions within the pulled-down complexes are inferred as a combination of spoke and matrix-modeled relationships. A socio-affinity index SA(u, v) then quantifies the tendency for two proteins u and v to identify each other when tagged (spoke model, S) and to co-purify when other proteins are tagged (matrix model, M):

      where, for the spoke model (S), is the number of times that u retrieves v when u is tagged; is the fraction of purifications when u was bait; is the fraction of all retrieved preys that were v; n_bait is the total number of purifications (i.e., using baits); and is the number of preys retrieved with u as bait. These terms are similarly defined for v as bait. For the matrix model (M), is the number of times that u and v are seen in purifications as preys with baits other than u or v; and are as above; and n_prey is the number of preys observed with a particular bait (excluding the bait itself).

      Friedel et al. [2009] combined the bait–prey relationships detected from the Gavin et al. [2006] and Krogan et al. [2006] experiments, and used a random sampling-based scheme to estimate confidence of interactions. In this approach, a list Φ= (ϕ₁, …, ϕn) purifications were generated where each purification ϕi consisted of one bait bi and the preys p_i,1, …, pi,m identified for this bait in the purification: ϕi = 〈bi, [p_i,1 …, pi,m]〉. From, Φ, l = 1000 bootstrap samples were created by drawing n purifications with replacement. This means that the bootstrap sample Sj(Φ) contains the same number of purifications as Φ and each purification ϕi can be contained in Sj(Φ) once, multiple times, or not at all, with multiple copies being treated as separate purifications. Interaction scores for the protein pairs are then calculated from these l bootstrap samples using socio-affinity scoring as above, where each protein pair is counted for the number of times the pair appeared across randomly sampled sets of interactions against what would be expected for the pair from random based on the abundance of each protein in the two datasets.

      Zhang et al. [2008] modeled each purification as a bit vector which lists proteins pulled down as preys against a bait across different experiments. The authors then used the Sørensen-Dice similarity index [Sørensen 1948, Dice 1945] between the vectors to estimate co-purification of preys across experiments, and thus the interaction reliability between proteins. Specifically, the pull-down data is transformed into a binary protein pull-down matrix in which a cell [u, i] in the matrix is 1 if u is pulled down as a prey in the experiment or purification i, and a zero otherwise. For two protein vectors in this matrix, the Sørensen-Dice similarity index, or simply the Dice coefficient, is computed as follows:

      where q is the number of the matrix elements (experiments or purifications) that have ones for both proteins u and v; r is the number of elements where u has ones, but v has zeroes; and s is the number of elements where v has ones, but u has zeroes. If u and v indeed interact (directly or as part of a complex), then most likely the two proteins will be frequently co-purified in different experiments. The Dice coefficient therefore estimates the fraction of times u and v are co-purified in order to estimate the interaction reliability between u and v.

      Hart et al. [2007] generated a Probabilistic Integrated Co-complex (PICO) network by integrating matrix-modeled relationships from the Gavin et al. [2002], Gavin et al. [2006], Krogan et al. [2006], and Ho et al. [2002] datasets using hypergeometric sampling. Specifically, the significance (p-value) for observing an interaction between the proteins u and v at least k times in the dataset is estimated using the hypergeometric distribution as

      where k is the number of times the interaction between u and v is observed, n and m are the total number of interactions for u and v, respectively, and N is the total number of interactions in the entire dataset. The lower the p-value, the lesser is the chance that the observed interaction between u and v is random, and therefore higher is the chance that the interaction is true.

      Methods such as Significance Analysis of INTeractome (SAINT) are based on quantitative analysis of mass spectrometry data. SAINT, developed by Choi et al. [2011] and Teo et al. [2014], assigns confidence scores to interactions based on the spectral counts of proteins pulled down in AP/MS experiments. The aim is to convert the spectral count Xij for a prey protein i identified in a purification of bait j into the probability of true interaction between the two proteins, P(True|Xij). For this, the true and false distributions,