An algorithm to detect complexes in PPI network based on harmony search clustering optimization

Abstract

The detection of complexes in protein–protein interaction (PPI) network bears great significance in predicting unknown protein and providing theoretical basis for various researches on a wide array of diseases. In this paper, a PPI network complexes detection algorithm based on Harmony Search Clustering Optimization Model (HMS-CD) is being proposed. Compared with the traditional harmony search algorithm, dynamic parameter of HMCR and BW is introduced to improve the search strategy. The method to find a set of nodes with a larger aggregation coefficient in PPI network is regarded as the objective function of the proposed algorithm. The experimental result on a real dataset like yeast PPI network shows that the proposed algorithm achieves better detection accuracy than traditional harmony search (HMS) algorithm and typical MCODE algorithm, and it can detect complexes in PPI network more effectively.

Keywords

Harmony search complexes detection PPI network

1. Introduction

Protein is an essential part in all cell and tissue structures of which serves as the executor of the physiological functions and is considered as the most important component in basic activities. A number of studies show that each protein in the cell does not exist in isolation but interacts with other proteins to fulfil its physiological functions. The network of interactions between proteins in organisms is called PPI (Protein–Protein Interaction) network. Current studies take protein network as an undirected graph. Each node consists of a protein, and each edge represents a pair of protein interaction. The PPI network is regarded as a kind of complex network which has a complex network topology structure feature, showing small-world and scale-free features (Watts et al. [14]). Studies have pointed out that the large-scale complex network, including biological network of significant modular characteristics, and a large number of protein complexes and functional modules (Graves et al. [5]) are shown in the PPI network. Those proteins connect to each other closely. Detecting complexes in the PPI network [13] help in predicting function of an unknown protein and providing an important theoretical basis of the research on disease prevention and treatment. According to the different implementation principles, the existing detection methods are mainly divided into four categories: based on (1) hierarchy [2], based on (2) density [1], based on (3) graph partitioning [20] and based on (4) core-attachment [3]. Some scholars have to adopt the intelligent algorithms such as Artificial Bee Colony Mechanism (Wu et al. [15]) and Ant Colony Clustering (Ji et al. [6]) to solve the problem of detecting functional modules in the PPI network.

Harmony Search (Geem et al. [4]) algorithm is a heuristic intelligent optimization algorithm designed by imitating the musicians playing wonderful music and has been successfully applied to many practical optimization problems such as Information network optimization (Mahdavi et al. [10]) and neural network training (Kulluk et al. [7]). Improved Harmony Search algorithm [9] has also been successfully designed for Automatic generation control of power system (Shiva et al. [12]), flowline manufacturing cell scheduling problem (Li et al. [8]) and other engineering problems. Similar to genetic algorithms that mimic biological evolution, the harmony search algorithm simulate the music playing with the variables of optimization problem corresponding to the music notes; the solution vectors corresponding to the harmony; the optimal solution corresponding to the beautiful sound and the optimization process corresponding to playing splendid music. The creation of a new harmony in the mechanism of the harmony search algorithm takes all the current harmony in harmony memory into account and adjusts to variables independent [18]. The biggest characteristic and advantage of this algorithm is that it can perform global both random searches and local searches as well [17].

Based on the advantage of the harmony search, the PPI network complexes detection algorithm based on Harmony Search Clustering Optimization Model (Harmony Search for Complexes Detection, HMS-CD) which is proposed in this paper aims to detect complexes clusters in the PPI network. The proposed algorithm overcomes the shortcomings of falling into local optimum easily by improving the search strategy of the traditional harmony search algorithm. It uses clustering coefficient of protein complex centre’s node to measure the clustering effect and impact the method of searching for the optimal clustering centre’s node as the objective function of the proposed algorithm to obtain the final detection result. The second section of this paper introduces the traditional harmony search (HMS) algorithm and the design of the objective function for the complexes detection in the PPI network which then introduces the framework of the proposed algorithm. In the third section, the result of experiment and analysis is presented. The fourth section summarizes the full text.

2. Proposed algorithm

This section introduces the traditional harmony search algorithm and the improved search strategy first and then applies the proposed algorithm to the studies of complexes detection in the PPI network. The objective function and the framework are therefore introduced toward the end of this section.

2.1. Design the complexes detection clustering model in PPI

Harmony Search algorithm is a kind of heuristic intelligent optimization algorithm. This algorithm initializes the harmony memory on a preset value scale firstly and next random search with the probability of HMCR in the harmony memory, then a new harmony is randomly generated by the probability of PAR and step length of $BW$ . If the new harmony is superior to the original harmony, the value of the original harmony will be replaced with the new harmony; randomly to generate a new harmony with probability of 1-HMCR out of the harmony memory and algorithm permission scope, if the new harmony is superior to the worst harmony in the harmony memory, the worst harmony will be replaced with the new harmony. The steps above is repeated until the end result is satisfactory. The algorithm performs local search ability around the initial position and then will search a new position by HMCR, PAR and $BW$ parameters. These parameters are usually set to constant, which will make the algorithm lack global search ability and fall into local optimum.

In this paper, the objective of the strategy in this proposed algorithm is to set the parameter of HMCR, PAR and $BW$ to enhance algorithm’s global search ability. In the early stage of iteration, the algorithm performs local search with smaller HMCR and PAR and larger $BW$ in expanding the search scope. The algorithm then adopts larger HMCR and smaller PAR and $BW$ when performing a local search. In the improved method, PAR is set to a smaller constant, and the dynamic $HMCR (t)$ instead of HMCR, and the dynamic $BW (t)$ instead of $BW$ is then introduced to the method. The calculation method is as shown in the formula (1): $\begin{matrix} (1) & \begin{matrix} HMCR (t) = {HMCR}_{\min} + \frac{1 - {HMCR}_{\min}}{t_{\max}} \times t \\ BW (t) = {BW}_{\min} \times (1 - \frac{t}{t_{\max}}) \end{matrix}\} . \end{matrix}$ Where, t represents the current iteration, $t_{\max}$ is the maximum number of iterations, $HMCR (t)$ is the t time’s iteration of the search probability on harmony memory. ${HMCR}_{\min}$ is the minimum search probability on harmony memory. $BW (t)$ is the perturbation step of the t time’s iteration, ${BW}_{\min}$ is the minimum perturbation step.

2.2. Designing the objective function of the proposed algorithm

One of the most important characteristics of biological data is that proteins with similar functions are linked to each other very closely. In the PPI network, the aggregation coefficient (Zhang et al. [19]) of each node reflects the aggregation degree of the node in the network. It is calculated by the number of real edges that exist on the adjacent nodes dividing by the number of possible edges, expressed in the formula (2): $\begin{matrix} (2) & coef (i) = \frac{2 n_{i}}{d_{i} (d_{i} - 1)} . \end{matrix}$ Where, i represents the node in the PPI network, $d_{i}$ expresses the number of edge between proteins that are adjacent with i, $n_{i}$ expresses the number of proteins that adjacent with i, $coef (i)$ represents the aggregation coefficient of i.

In this paper, the method of searching for the optimal cluster center node is regarded as the objective function and the aggregation coefficient of the center node is used to evaluate the clustering effect. The larger the aggregation coefficient of the center node is, the closer the connection between the proteins in the complexes is and it is likelier that these proteins belong to the same complexes.

2.3. Algorithm of harmony search clustering optimization model

By improving the search strategy of the traditional harmony search algorithm, the harmony search clustering optimization model is proposed and applied for the complexes detection in the PPI network. The algorithm passes through certain phases. Firstly, it needs to initialize and work out the quantity of all nodes in the PPI network and identifying the number on these nodes one by one which is a benefit for improving the efficiency of the algorithm. The proposed algorithm begins with initializing the HMS. Each HMS stores a harmony corresponding to the centre’s node of a certain complexes cluster, then search a new harmony as the centre’s node of this cluster with probability of HMCR and the edge aggregation coefficient of the centre’s node is calculated as the objective function value. If the new objective function value is better than the value of the original node, replace the original node with the new one. Keep searching for the new harmony until the algorithm termination conditions are met which means all the objective function value of HMS is greater than the given threshold ( ${COEF}_{\max}$ ) or once the numbers of iteration have reached the maximum value. Finally, the results of complexes detection are obtained.

According to the above description, the specialized process of the proposed complexes detection algorithm based on Harmony Search clustering optimization model is shown in Algorithm 1.

Algorithm 1

The Framework of HMS-CD

3. Result and discussion

This paper takes the yeast protein–protein interaction network as the research object. The PPI network data for experiment are from DIP (Xenarios et al. [16]), including 5093 proteins, 24743 interactive edges, and the protein complexes data used for experimental comparison come from CYC2008 (Pu et al. [11]) which contains 408 complexes.

3.1. Evaluation method of complexes detection

The selection of an appropriate evaluation method for complexes detection in the PPI network is the most important. Different methods will generate different results. Even the same method with a different parameter value will also generate different results. Now the most widely used evaluation indicator is precision and recall.

Precision is the ratio of the maximum matching of data set that map the result of experimental data set to standard data sets and the experimental data set. Formula (3) as follows: $\begin{matrix} (3) & precision = \frac{| X \cap F_{i} |}{| X |} \end{matrix}$

Recall is the ratio of the maximum matching of data set that map the result of the experimental data set to standard data sets and the standard data set. Formula (4) as follows: $\begin{matrix} (4) & recall = \frac{| X \cap F_{i} |}{| F_{i} |} \end{matrix}$

Among them x is one of the experiment result date sets, $F_{i}$ is one of the standard result sets.

In general, the more nodes the result data set of the experiment has, the higher the recall tends to be. On the contrary, the less nodes, the higher the precision is. In this paper, the harmonic means of the precision and recall is used to measure the performance of a method synthetically. It is computed as follows: $\begin{matrix} (5) & f - measure = \frac{2}{\frac{1}{precision} + \frac{1}{recall}} \end{matrix}$

3.2. Parameter setting

In the proposed algorithm, the function of perturbation probability (PAR) is to determine whether the local search is performed or not. As a smaller PAR readily increases the possibility of local search, the PAR is set to 0.03 in the experiment. If the current iteration number reaches the maximum iterations, the algorithm will be terminated. In the experiment, the parameter MAXITE of maximum iterations was set to 5000. The 5-fold cross validation was carried out in the experiment. When ${COEF}_{\max}$ was set to 0.5, the result of correct, precision, recall and f-measure of experimental with different HMS value is showed on Table 1.

Table 1
Experiment Result of ${COEF}_{\max} = 0.5$

HMS correct precision recall f-measure

10 0.9000 0.6004 0.539 0.5661

30 0.9470 0.5728 0.5899 0.5785

50 0.9360 0.5631 0.6062 0.5828

60 0.9370 0.5491 0.5879 0.5675

70 0.9457 0.4973 0.557 0.5253

90 0.9470 0.4921 0.5748 0.5298

100 0.9620 0.4393 0.5501 0.488

200 0.9620 0.3857 0.5893 0.4659

300 0.9500 0.3217 0.5563 0.4075

400 0.9535 0.2897 0.5459 0.3784

500 0.9404 0.2745 0.5196 0.3591

600 0.9283 0.2586 0.5049 0.342

800 0.8918 0.2455 0.4576 0.3193

1000 0.8628 0.2462 0.4316 0.3136

HMS	correct	precision	recall	f-measure
10	0.9000	0.6004	0.539	0.5661
30	0.9470	0.5728	0.5899	0.5785
50	0.9360	0.5631	0.6062	0.5828
60	0.9370	0.5491	0.5879	0.5675
70	0.9457	0.4973	0.557	0.5253
90	0.9470	0.4921	0.5748	0.5298
100	0.9620	0.4393	0.5501	0.488
200	0.9620	0.3857	0.5893	0.4659
300	0.9500	0.3217	0.5563	0.4075
400	0.9535	0.2897	0.5459	0.3784
500	0.9404	0.2745	0.5196	0.3591
600	0.9283	0.2586	0.5049	0.342
800	0.8918	0.2455	0.4576	0.3193
1000	0.8628	0.2462	0.4316	0.3136

It is not difficult to find out that the algorithm achieves higher accuracy, up to 85% complexes can be obtained, and the advantage of the proposed algorithm is apparent. With the increase as the value of HMS, more complexes are obtained; the proportion of effective complexes will be smaller, and precision value will be decreased. Instead, the protein of matching rate that in known complexes will increase, thus, the recall value will show a rising trend. Therefore, when the HMS value is 50, the value of f-measure is larger, and the detection results are better.

Next, the effect of ${COEF}_{\max}$ was considered in the experiment under $HMS = 50$ . Experiments were performed independently for 20 times, the influence of ${COEF}_{\max}$ on precision, recall is shown in Figs 1 and 2.

Fig. 1.

Influence of ${COEF}_{\max}$ on precision.

Fig. 2.

Influence of ${COEF}_{\max}$ on recall.

The greater the value of ${COEF}_{\max}$ is means the closer the complexes clustering is. And the smaller the value is, the faster the algorithm converges. Then, the influence of ${COEF}_{\max}$ on f-measure is shown in Fig. 3.

Fig. 3.

Influence of ${COEF}_{\max}$ on f-measure.

From the experimental result as shown in Fig. 1 to Fig. 3 that when ${COEF}_{\max}$ is 0.75, the value of f-measure is larger, which means the algorithm gets better precision and recall simultaneously and achieves best experiment effect.

3.3. Validity analysis

In this paper, the algorithm was improved on the basis of the traditional harmony search algorithm (HMS). In order to verify the effectiveness of the improved algorithm parameters, the proposed HMS-CD algorithm was compared with the HMS algorithm through experiments. The experiments were carried out independently for 20 times, take the average of each experiment result as a comparison value, the result of precision, recall and f-measure under $HMCR = 50$ are shown in Fig. 4 and Fig. 5.

Fig. 4.

Compared between HSM-CD and HMS on precision.

Fig. 5.

Compared between HSM-CD and HMS on recall.

Fig. 6.

Compared between HSM-CD and HMS on f-measure.

From the experimental result as shown in Fig. 4 to Fig. 5, compared the HMS algorithm, the proposed HSM-CD algorithm achieves higher value of precision and recall. Next, the influence of f-measure is shown in Fig. 6.

Figure 6 shows the comparative result on the value of f-measure, the proposed HMS-CD algorithm achieves higher value than HMS algorithm. It fully proves the effect of parameter improvement.

In order to verify the effectiveness of the complexes detection, the proposed HMS-CD algorithm was compared with the HMS algorithm and the MCODE (Bader et al. [1]) algorithm which is based on the density of the typical, The experiments were carried out independently for 10 times, the result of average value is shown in Fig. 7.

Fig. 7.

Compared HSM-CD with HMS and MCODE on f-measure.

As it can be seen in Fig. 7, the proposed HMS-CD algorithm achieves higher value of f-measure. It fully concludes the performance of this algorithm and the effectiveness of complexes detection in the PPI network.

4. Conclusion and future work

In this paper, by improving and applying the traditional harmony search to detect complexes in PPI network, an algorithm for complexes detection in protein–protein interaction network based on harmony search clustering optimization has been presented. The experimental results show that the proposed algorithm not only has an ability for local searches but also has stronger the ability for global searches. Next work is to verify the reliability of the algorithm on a number of data sets, and the further optimization with algorithm time complexity shall be done.

Footnotes

Acknowledgement

This work was supported in part by the National Natural Science Foundation of China (No. 41362015) and Science & Technology Projects of Department of Education of Jiangxi Province (Grant Nos. GJJ14431, GJJ14432, GJJ14434 and GJJ14458).

References

G.D.

Bader and

C.W.V.

Hogue, An automated method for finding molecular complexes in large protein interaction networks, BMC Bioinformatics 4(2) (2003).

Y.-R.

Cho,

Hwang,

Ramanathan and

Zhang, Semantic integration to identify overlapping functional modules in protein interaction networks, BMC Bioinformatics 8 (2007), 265.

A.J.

Enright,

Van Dongen and

C.A.

Ouzounis, An efficient algorithm for large-scale detection protein families, Nucleic Acids Research 30(7) (2002), 1575–1584. doi:10.1093/nar/30.7.1575.

Z.W.

Geem,

J.H.

Kim and

G.V.

Loganathan, A new heuristic optimization algorithm: Harmony search, Simulation 76(2) (2001), 60–68. doi:10.1177/003754970107600201.

P.R.

Graves and

T.A.

Haystead, Molecular biologist’s guide to proteomics, Microbiology and Molecular Biology Reviews 66(1) (2002), 39–63. doi:10.1128/MMBR.66.1.39-63.2002.

Ji,

Liu,

Zhang and

Liu, ACC-FMD: Ant colony clustering for functional module detection in protein–protein interaction networks, International Journal of Data Mining and Bioinformatics 11(3) (2015), 331–363. doi:10.1504/IJDMB.2015.067323.

Kulluk,

Ozbakir and

Baykasoglu, Training neural networks with harmony search algorithms for classification problems, Engineering Applications of Artificial Intelligence 25(1) (2012), 11–19. doi:10.1016/j.engappai.2011.07.006.

Li,

Li and

J.N.D.

Gupta, Solving the multi-objective flowline manufacturing cell scheduling problem by hybrid harmony search, Expert Systems With Applications 42(3) (2015), 1409–1417. doi:10.1016/j.eswa.2014.09.007.

Lu and

He, Improvement and application of harmony search algorithm, Computer Science & Education (2015), 967–970.

10.

Mahdavi,

Haghir Chehreghani,

Abolhassani and

Forsati, Novel meta-heuristic algorithms for clustering web document, Applied Mathematics and Computation 1(2) (2008), 441–451. doi:10.1016/j.amc.2007.12.058.

11.

et al., Up-to-date catalogues of yeast protein complexes, Nucleic Acdis Research 37(3) (2009), 825–831. doi:10.1093/nar/gkn1005.

12.

C.K.

Shiva,

Shankar and

Mukherjee, Automatic generation control of power system using a novel quasi-oppositional harmony search algorithm, International Journal of Electrical Power & Energy Systems 73(1) (2015), 787–804. doi:10.1016/j.ijepes.2015.05.048.

13.

Srinivasa Rao,

Srinivas,

G.N.

Sujini and

Kumar, Protein–protein interaction detection: Methods and analysis, International Journal of Proteomics (2014).

14.

D.J.

Watts and

S.H.

Strogatz, Collective dynamics of ‘small-world’ networks, Nature 393 (1998), 440–442.

15.

Wu,

Lei and

Tian, Clustering PPI network based on function flow model through artificial bee colony algorithm, in: 2011 Seventh International Conference on Natural Computation, 2011, pp. 92–96. doi:10.1109/ICNC.2011.6022073.

16.

Xenarios

et al., DIP: The database of interaction proteins, Nucleic Acids Research 28(1) (2000), 289–291. doi:10.1093/nar/28.1.289.

17.

Yadav,

Yadav and

J.H.

Kim, A study of harmony search algorithms: Exploration and convergence ability, in: Advances in Intelligent System and Computing, Vol. 382, 2016, pp. 53–62.

18.

Yan,

Duan,

Zhang,

Chen and

Pan, Harmony search algorithm with self-adaptive dynamic parameters, in: The 27th Chinese Control and Decision Conference, 2015, pp. 1221–1226.

19.

Zhang, Protein Interaction Networks, Cambridge University Press, New York, 2009.

20.

Zhao,

Wang,

Li,

F.-X.

Wu and

Pan, Detecting protein complexes based on uncertain graph model, IEEE/ACM Tracsactions On Computational Biology And Bioinformatics 11(3) (2014), 486–497. doi:10.1109/TCBB.2013.2297915.