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

organizational, or evolutionary evidence on complexes or their constituent proteins. Wang et al. [2010] and Chen et al. [2014] present alternative classifications based on topological (interaction density, betweenness centrality, and clustering coefficient), and dynamical properties of PPI networks capitalized by computational methods, respectively.

      We present this classification of methods for protein complex prediction as two snapshots—methodology-based and chronology-based—as shown in Figures 3.1 and 3.2, respectively. The methodology-based classification (Figure 3.1) is based on algorithmic methodologies employed by the methods. At level 1 of the tree, we divide methods into those based solely on network clustering, and those employing additional biological information. At subsequent levels, we further subdivide the methods based on their algorithmic strategies into: (i) methods employing merging or growing of clusters from the network (agglomerative); and (ii) methods employing repeated partitioning of the network (divisive). Agglomerative methods go bottom-up, i.e., by beginning with small “seeds” (e.g., triangles or cliques) and repeatedly adding proteins or merging clusters of proteins based on certain similarity criteria to arrive at predicted set of complexes. On the other hand, divisive methods go top-down, i.e., by repeatedly partitioning the network into multiple dense subnetworks based on certain dissimilarity criteria to arrive at predicted complexes. In the chronology-based classification (Figure 3.2), we bin methods based on the time (year) when these were developed, and for each bin we stack the methods based on the kind of biological information they employ for the prediction.

      Figures 3.1 and 3.2 and Table 3.1 show only the methods that are discussed in this chapter. Other methods that employ diverse kinds of biological information and/or algorithmic strategies are covered in the following chapters.

3.3 Methods Based Solely on PPI Network Clustering

      Most methods that directly mine for dense subnetworks from the PPI network make use of solely the topology of the network.

       Molecular COmplex DEtection (MCODE)

      MCODE, proposed by Bader and Hogue [2003], is one of the first computational methods developed for protein complex detection from PPI networks. The MCODE algorithm operates in two steps, vertex weighting and complex prediction, and an optional third step for post-processing of the candidate complexes. In the first step, each protein v in the PPI network G is weighted based on its clustering coefficient (CC). However, instead of using the entire neighborhood of v, MCODE uses the density of the highest k-core in the neighborhood of v, which amplifies the weights for proteins located in densely connected regions of G. A k-core is a subnetwork of proteins such that each protein in this subnetwork has a degree no less than k. A k-core in the neighborhood of v is a subnetwork of v and all its neighbors that have degree no less than k. A k-core in the neighborhood of v is highest or maximal if there exists no (k + 1)-core in that neighborhood. If Ck(v) represents this highest k-core, the weight for v is assigned as: