Related Work

Unsupervised algorithms

Over 30 unsupervised clustering algorithms have extensively been applied to the problem of protein complex detection from PPINs. The 3 most famous unsupervised algorithms are:

• Molecular Complex Detection (MCODE) by Bader and Hogue [1] in 2003: One of the earliest algorithms, MCODE first weights each vertex based on the density of its neighborhood. Then it moves outward from the highest weighted vertex, adding vertices in its neighborhood with weights higher than a threshold.
• Markov Clustering (MCL) by Dongen et al. [2] in 2000 is a flow-based method, employing random walks by modifying the adjacency matrix using expansion and inflation operators. These increase the probability of intracluster walks and decrease the probability of inter-cluster walks respectively. This method has been one of the most popular algorithms, albeit it producing non-overlapping clusters only.
• Clustering with Overlapping Neighborhood Expansion (ClusterOne) by Nepusz et al. [3] in 2012 is based on seeding and greedy growth.

Supervised Algorithms

In the past, only 7 supervised strategies have been applied to the current problem. The major steps for most of the algorithms is the same, broadly - feature extraction, ML model and subgraph sampling. The main characteristics of each of these methods are outlined below:

• The earliest method was by Qi et al. [4] in 2008 using 33 features (29 topological & 4 biological), ML models - bayesian network (SCI-BN) and support vector machines (SCI-SVM), and a seeding approach - iterative simulated annealing (ISA) for candidate subgraph selection.
• Recursively trained two-layer feed-forward neural-network model by Shi et al. [5] in 2011.
• Complex Detection based on Integrated Properties (CDIP) by Yu et al. [6] in 2011. CDIP utilizes 32 features (12 topological and 20 biological) to define a similarity measure (cosθ) between proteins, and an additional topological constraint measuring connectivity of a vertex to the subgraph. Both of these are used for scoring subgraphs, obtained through a seeding and growth method.
• Supervised learning protein complex detection (SLPC) by Ying Yu et al. [7] in 2014: SLPC uses a regression model (RM) with 10 topological features, solved by gradient descent. Opposed to the previous seeding approaches, a modified Cliques algorithm was implemented to find candidate subgraphs.
• ClusterEPs proposed by Liu et al. [8] in 2016: ClusterEPs uses a score function based on noise-tolerant emerging patterns (NEPs) - minimal feature sets that are representative of a complex and are discriminatory between complexes and random subgraphs (negative set). Following this, a search process based on seeding and growing clusters based on highest degree is employed to identify high scoring complexes.
• ClusterSS proposed by Dong et al. [9] in 2018 uses a neural network with one hidden layer and 17 features, and a new score function for the search process based on seeding, with an introduced acceleration step called top-k. Top-k essentially goes through only the top k exterior nodes by degree to select a new node for growing the cluster; and similarly top-k existing nodes for deletion based on the score function. The new score function comprises of an output score from the neural network and a structural score, which is the fraction of intra - subgraph edge weights of subgraph nodes and total edge weights of subgraph nodes.
• Sikandar et al. [10] in 2018 propose three decision tree methods, using 65 features (13 topological, rest biological) as the non-leaf nodes in the tree. The leaf nodes indicate complexes, the edge weights indicate feature values and the tree structure is obtained by training on a known set of complexes. For complex identification, proteins of the PPIN are assigned to complexes by tree-traversal.

References

[1] Bader, G. D. and Hogue, C. W. V. (2003). An automated method for finding molecular complexes in large protein interaction networks. BMC bioinformatics, 4:2.

[2] Van Dongen, S. M. (2000). Graph clustering by flow simulation (Doctoral dissertation).

[3] Nepusz, T., Yu, H., and Paccanaro, A. (2012). Detecting overlapping protein complexes in protein-protein interaction networks. Nature methods, 9(5):471–2.

[4] Qi, Y., Balem, F., Faloutsos, C., Klein-Seetharaman, J., and Bar-Joseph, Z. (2008). Protein complex identification by supervised graph local clustering. Bioinformatics (Oxford, England), 24(13):250–8.

[5] Shi, L., Lei, X., and Zhang, A. (2011). Protein complex detection with semi-supervised learning in protein interaction networks. Technical report.

[6] Yu, Y., Lin, L., Sun, C., Wang, X., and Wang, X. (2011). Complex Detection Based on Integrated Properties. pages 121–128. Springer, Berlin, Heidelberg.

[7] Dong, Y., Sun, Y., and Qin, C. (2018). Predicting protein complexes using a supervised learning method combined with local structural information. PLOS ONE, 13(3):e0194124.

[8] Liu, Q., Song, J., and Li, J. (2016). Using contrast patterns between true complexes and random subgraphs in PPI networks to predict unknown protein complexes OPEN.

[9] Ying Yu, F., Hao Yang, Z., Tang, N., Fei Lin, H., Wang, J., and Wei Yang, Z. (2014). Predicting protein complex in protein interaction network - a supervised learning based method. Technical report.

[10] Sikandar, A., Anwar, W., Bajwa, U. I., Wang, X., Sikandar, M., Yao, L., Jiang, Z. L., and Chunkai, Z. (2018). Decision Tree Based Approaches for Detecting Protein Complex in Protein Protein Interaction Network (PPI) via Link and Sequence Analysis. IEEE Access, 6:22108–22120.