The bat algorithm was used to detect the functional modules in protein-protein interaction networks (PPINs), in order to get better protein functional modules and reveal the function of proteins. The position of each bat individual represents a candidate functional module partition. Each protein node in PPIN and all its neighbor nodes form an ordered adjacency list and the population is initialized by random walk coding method in the ordered adjacency list. Four kinds of optimization mechanisms, namely directional local disturbance, random disturbance, adaptive variation based on distance and frequency, natural selection, are designed for the random optimization of solutions in the process of population optimization. The comparison experiments of the proposed algorithm and six classical algorithms were conducted on five yeast PPIN datasets having different scales. Results showed that many functional modules detected by the proposed method matched the standard modules and the evaluation indexes including coverage, recall, sensitivity, positive predictive value and accuracy were outstanding, which verified the validity of the proposed method.
Jia-hao XU,Jun-zhong JI,Cui-cui YANG. Functional modules detection based on bat algorithm in protein-protein interaction networks. Journal of ZheJiang University (Engineering Science), 2019, 53(8): 1618-1629.
Fig.1Example of protein-protein interaction network
Fig.2Ordered adjacency list in initialization of bat individual
Fig.3Encoding of bat individual position in BA-FMD algorithm
Fig.4Functional modules after decoding of bat individual position in BA-FMD algorithm
Fig.5Schematic diagram of directional local disturbance operation of bat individual in BA-FMD algorithm
Fig.6Schematic diagram of random disturbance operation of bat individual in BA-FMD algorithm
数据集
节点数目
边数目
Gavin
1 430
6 531
DIPcore
2 508
5 673
Krogan
3 672
14 317
Collins
1 622
9 074
BioGRID
5 640
59 748
Tab.1Number of nodes and edges for Gavin, DIPcore, Krogan, Collins and BioGRID datasets
数据集
ε
δ
Gavin
0.24
0.04
DIPcore
0.36
0.04
Krogan
0.30
0.04
Collins
0.36
0.04
BioGRID
0.24
0.18
Tab.2Connection similarity threshold and filtering threshold on different datasets in BA-FMD algorithm
Fig.7Optimal individual fitness of BA-FMD algorithm for convergence under different population sizes
Fig.8Values of evaluation indexes under different combined thresholds in BA-FMD algorithm
算法
数据集
结果
模块数
模块平均大小
Na≥0.2
Nb≥0.2
BA-FMD
Gavin
215
6.48
111
198
DIPcore
416
6.01
163
252
Krogan
521
6.93
135
190
Collins
291
5.45
148
244
BioGRID
731
6.02
218
295
NACO-FMD
Gavin
115
7.31
80
163
DIPcore
311
5.00
125
209
Krogan
183
2.81
77
115
Collins
254
3.58
129
162
BioGRID
195
3.21
72
92
BFO-FMD
Gavin
146
6.57
94
176
DIPcore
302
6.29
153
246
Krogan
189
7.04
80
145
Collins
268
5.63
148
252
BioGRID
281
5.73
140
220
Jerarca
Gavin
259
5.39
99
174
DIPcore
583
4.34
151
230
Krogan
727
4.05
101
167
Collins
385
4.21
150
245
BioGRID
1 313
4.30
98
156
COACH
Gavin
324
2.34
122
197
DIPcore
381
2.87
136
155
Krogan
579
9.29
247
190
Collins
251
18.02
176
199
BioGRID
1 507
22.85
410
264
ClusterONE
Gavin
243
5.92
102
156
DIPcore
269
4.13
115
157
Krogan
240
4.68
100
139
Collins
203
6.44
118
201
BioGRID
475
6.56
163
219
ClusterEPs
Gavin
297
5.03
171
165
DIPcore
354
4.72
208
182
Krogan
494
6.62
297
178
Collins
173
9.82
132
170
BioGRID
822
5.50
396
252
Tab.3Experimental results of seven algorithms on five datasets
Fig.9Comparison of different evaluation indexes of seven algorithms on five datasets
[1]
UHLéN M, FAGERBERG L, HALLSTR?M B M, et al Tissue-based map of the human proteome[J]. Science, 2015, 347 (6220): 1260419
doi: 10.1126/science.1260419
[2]
AKOADJEI D, FU W, WALLIN C, et al HIV-1, human interaction database: current status and new features[J]. Nucleic Acids Research, 2015, 43 (D1): 566- 570
doi: 10.1093/nar/gku1126
[3]
LUO J W, LI C A novel method to predict protein complexes based on Gene Ontology in PPI networks[J]. Journal of Computational Information Systems, 2013, 9 (12): 5031- 5039
[4]
JI J Z, ZHANG A D, LIU C N, et al Survey: functional module detection from protein-protein interaction networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26 (2): 261- 277
doi: 10.1109/TKDE.2012.225
[5]
李敏, 孟祥茂 动态蛋白质网络的构建、分析及应用研究进展[J]. 计算机研究与发展, 2017, 54 (6): 1281- 1299 LI Min, MENG Xiang-mao The construction, analysis, and applications of dynamic protein-protein interaction networks[J]. Journal of Computer Research and Development, 2017, 54 (6): 1281- 1299
doi: 10.7544/issn1000-1239.2017.20160902
[6]
冀俊忠, 刘志军, 刘红欣, 等 蛋白质相互作用网络功能模块检测的研究综述[J]. 自动化学报, 2014, 40 (4): 577- 593 JI Jun-zhong, LIU Zhi-jun, LIU Hong-xin, et al An overview of research on functional module detection for protein-protein interaction networks[J]. Acta Automatica Sinica, 2014, 40 (4): 577- 593
[7]
WU M, LI X L, KWOH C K, et al A core-attachment based method to detect protein complexes in PPI networks[J]. BMC Bioinformatics, 2009, 10 (1): 169- 178
doi: 10.1186/1471-2105-10-169
[8]
ALDECOA R, MARIN I Jerarca: efficient analysis of complex networks using hierarchical clustering[J]. Plos One, 2010, 5 (7): e11585
doi: 10.1371/journal.pone.0011585
[9]
NEPUSZ T, YU H, PACCANARO A Detecting overlapping protein complexes in protein-protein interaction networks[J]. Nature Methods, 2012, 9 (5): 471- 472
doi: 10.1038/nmeth.1938
[10]
LIU Q Z, SONG J N, LI J Y Using contrast patterns between true complexes and random subgraphs in PPI networks to predict unknown protein complexes[J]. Scientific Reports, 2016, 6: 21223
doi: 10.1038/srep21223
[11]
JI J Z, LIU Z J, ZHANG A D, et al. Improved ant colony optimization for detecting functional modules in protein-protein interaction networks [C]// International Conference on Information Computing and Applications. Berlin: Springer, 2012: 404-413.
[12]
JI J Z, LV J W, YANG C C, et al Detecting functional modules based on a multiple-grain model in large-scale protein-protein interaction networks[J]. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2015, 13 (4): 610- 622
[13]
YANG C C, JI J Z, ZHANG A D BFO-FMD: bacterial foraging optimization for functional module detection in protein-protein interaction networks[J]. Soft Computing, 2018, 22 (10): 3395- 3416
doi: 10.1007/s00500-017-2584-9
[14]
马杰, 沈钧贤, 赵辉华, 等 回声定位蝙蝠及其声通讯[J]. 动物学杂志, 2002, 37 (6): 79- 82 MA Jie, SHEN Jun-xian, ZHAO Hui-hua, et al Echolocation and acoustic communication in bats[J]. Chinese Journal of Zoology, 2002, 37 (6): 79- 82
doi: 10.3969/j.issn.0250-3263.2002.06.021
[15]
YANG X S A new metaheuristic bat-inspired algorithm[J]. Computer Knowledge and Technology, 2010, 284: 65- 74
[16]
JAYABARATHI T, RAGHUNATHAN T, GANDOMI A H The bat algorithm, variants and some practical engineering applications: a review[J]. Studies in Computational Intelligence, 2018, 744: 313- 330
[17]
THARAKESHWAR T K, SEETHARAMU K N, PRASAD B D Multi-objective optimization using bat algorithm for shell and tube heat exchangers[J]. Applied Thermal Engineering, 2017, 110: 1029- 1038
doi: 10.1016/j.applthermaleng.2016.09.031
[18]
JENSI R, WISELIN J G MBA-LF: a new data clustering method using modified bat algorithm and levy flight[J]. ICTACT Journal on Soft Computing, 2015, 6 (1): 1093- 1101
doi: 10.21917/ijsc
[19]
CHENG C Y, BAO C H. A kernelized fuzzy c-means clustering algorithm based on bat algorithm [C]// International Conference on Computer and Automation Engineering. Brisbane: ACM, 2018: 1-5.
[20]
JADDI N S, ABDULLAH S, HAMDAN A R Multi-population cooperative bat algorithm-based optimization of artificial neural network model[J]. Information Sciences, 2015, 294: 628- 644
doi: 10.1016/j.ins.2014.08.050
[21]
LU S, QIU X, SHI J, et al A pathological brain detection system based on extreme learning machine optimized by bat algorithm[J]. CNS and Neurological Disorders-Drug Targets, 2017, 16 (1): 23- 29
doi: 10.2174/1871527315666161019153259
[22]
CHEN Z M, BO Y M, TIAN M C, et al Dynamic perceptive bat algorithm used to optimize particle filter for tracking multiple targets[J]. Journal of Aerospace Engineering, 2018, 31 (3): 04018015
doi: 10.1061/(ASCE)AS.1943-5525.0000834
