Please wait a minute...
浙江大学学报(工学版)  2019, Vol. 53 Issue (8): 1618-1629    DOI: 10.3785/j.issn.1008-973X.2019.08.021
化学工程、生物工程     
基于蝙蝠算法的蛋白质网络功能模块检测
徐嘉豪(),冀俊忠*(),杨翠翠
北京工业大学 多媒体与智能软件技术北京市重点实验室,北京 100124
Functional modules detection based on bat algorithm in protein-protein interaction networks
Jia-hao XU(),Jun-zhong JI*(),Cui-cui YANG
Beijing Municipal Key Laboratory of Multimedia and Intelligent Software Technology, Beijing University of Technology, Beijing 100124, China
 全文: PDF(1217 KB)   HTML
摘要:

为了得到更好的蛋白质功能模块,揭示蛋白质的功能,利用蝙蝠算法对蛋白质相互作用网络(PPINs)进行功能模块检测. 每个蝙蝠个体所在的位置代表一种候选的功能模块划分,将PPIN中每个蛋白质节点与其所有邻居节点组成邻居有序表,采用在邻居有序表中随机游走的编码方式进行种群的初始化;在种群优化过程中,设计定向局部扰动、随机扰动、基于距离和频率的自适应变异、自然选择4种寻优机制来进行解的随机优化. 在5个不同规模的酵母菌PPIN数据集上,将所提出方法与6种经典算法进行对比实验. 结果表明,所提出方法检测到的功能模块中有较多模块与标准模块相匹配,并且所提出算法在覆盖率、召回率、灵敏度、正的预测率、准确度评价指标上均表现突出,验证了所提出方法的有效性.

关键词: 蛋白质相互作用网络(PPIN)功能模块检测蝙蝠算法扰动自适应变异自然选择    
Abstract:

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.

Key words: protein-protein interaction network (PPIN)    functional module detection    bat algorithm    disturbance    adaptive variation    natural selection
收稿日期: 2018-07-11 出版日期: 2019-08-13
CLC:  Q 811  
通讯作者: 冀俊忠     E-mail: xjh8239@163.com;jjz01@bjut.edu.cn
作者简介: 徐嘉豪(1994—),女,硕士生,从事生物信息学研究. orcid.org/0000-0002-8043-1104. E-mail: xjh8239@163.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  
徐嘉豪
冀俊忠
杨翠翠

引用本文:

徐嘉豪,冀俊忠,杨翠翠. 基于蝙蝠算法的蛋白质网络功能模块检测[J]. 浙江大学学报(工学版), 2019, 53(8): 1618-1629.

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.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2019.08.021        http://www.zjujournals.com/eng/CN/Y2019/V53/I8/1618

图 1  蛋白质相互作用网络示例
图 2  蝙蝠个体初始化时的邻居有序表
图 3  BA-FMD算法中蝙蝠个体的位置编码
图 4  BA-FMD算法中蝙蝠个体位置解码后的功能模块
图 5  BA-FMD算法中蝙蝠个体定向局部扰动操作示意图
图 6  BA-FMD算法中蝙蝠个体随机扰动操作示意图
数据集 节点数目 边数目
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
表 1  Gavin、DIPcore、Krogan、Collins、BioGRID数据集的节点与边数目
数据集 ε δ
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
表 2  BA-FMD算法在不同数据集上的连接相似度阈值和过滤阈值
图 7  BA-FMD算法在不同种群规模下达到收敛时的最优个体适应度
图 8  BA-FMD算法在不同合并阈值下评价指标的取值
算法 数据集 结果
模块数 模块平均大小 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
表 3  7种算法在5个数据集上的实验结果
图 9  7种算法在5个数据集上的不同评价指标比较
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
[1] 王灿,凌道盛,王恒宇. 软土结构性对基坑开挖及邻近地铁隧道的影响[J]. 浙江大学学报(工学版), 2020, 54(2): 264-274.
[2] 张程,金涛,李培强,邓慧琼. 采用多目标蝙蝠算法的电力系统广域协调控制策略[J]. 浙江大学学报(工学版), 2019, 53(3): 589-597.
[3] 袁海辉,葛一敏,甘春标. 不确定性扰动下双足机器人动态步行的自适应鲁棒控制[J]. 浙江大学学报(工学版), 2019, 53(11): 2049-2057.
[4] 何杰光, 彭志平, 崔得龙, 李启锐. 局部维度改进的教与学优化算法[J]. 浙江大学学报(工学版), 2018, 52(11): 2159-2170.
[5] 朱卓悦, 徐志刚, 沈卫东, 杨得玉. 基于遗传蝙蝠算法的选择性拆卸序列规划[J]. 浙江大学学报(工学版), 2018, 52(11): 2120-2127.
[6] 吴新忠, 邢强, 陈明, 成江洋, 杨春雨. 采用改进互补集总经验模态分解的电能质量扰动检测方法[J]. 浙江大学学报(工学版), 2017, 51(9): 1834-1843.
[7] 周华, 陈丽, 段登平. 基于滑模变结构的欠驱动浮空器轨迹跟踪控制[J]. 浙江大学学报(工学版), 2017, 51(7): 1412-1420.
[8] 毕晓君, 王佳荟. 基于混合学习策略的教与学优化算法[J]. 浙江大学学报(工学版), 2017, 51(5): 1024-1031.
[9] 郭凡, 魏建华, 张强, 熊义. 基于级联控制器的液压机位移/压力复合控制[J]. 浙江大学学报(工学版), 2017, 51(10): 1937-1947.
[10] 王日俊, 白越, 续志军, 宫勋, 张欣, 田彦涛. 基于扰动观测器的多旋翼无人机机载云台模糊自适应跟踪控制[J]. 浙江大学学报(工学版), 2015, 49(10): 2005-2012.
[11] 安通鉴,刘祥官. 目标轨迹更新的点到点鲁棒迭代学习控制[J]. 浙江大学学报(工学版), 2015, 49(1): 87-92.
[12] 杨滔, 吕征宇. 三相光伏系统中一种新的最大功率点追踪方法[J]. J4, 2012, 46(8): 1490-1497.
[13] 钟琮玮, 项基, 韦巍, 张远辉, 陈鹏. 基于扰动观测器的机械手碰撞检测与安全响应[J]. J4, 2012, 46(6): 1115-1121.
[14] 徐日庆,张俊,朱剑锋, 王兴陈. 考虑扰动影响的修正Duncan-Chang模型[J]. J4, 2012, 46(1): 1-7.
[15] 朱剑锋, 徐日庆, 王兴陈. 基于扰动状态概念模型的刚性挡土墙土压力理论[J]. J4, 2011, 45(6): 1081-1087.