基于烟花算法的蛋白质相互作用网络功能模块检测方法
|
摘要
针对群智能聚类方法在蛋白质相互作用网络功能模块检测问题上运行时间长的不足,本文提出了一种基于烟花算法的蛋白质相互作用网络功能模块检测方法(Fireworks Algorithm for Functional Module Detection in Protein-protein Interaction Networks,简称FWA-FMD).首先结合蛋白质相互作用网络的拓扑结构信息和基因本体的功能注释信息,基于标签传播思想将每个烟花个体初始化为一种候选的功能模块划分.其次在每一代进化过程中,利用具有局部搜索和全局搜索自调整能力的爆炸操作对每个烟花个体进行优化,并同时采用精英保留和轮盘赌策略选择下一代烟花个体.最后通过将最优烟花个体中标签相同的节点划分到同一功能模块,以得到最终的功能模块检测结果.在酵母菌和人类两个物种的4个公共蛋白质相互作用网络数据集上的功能模块检测结果,分别用两种标准功能模块数据集作为基准来评价的实验表明:FWA-FMD算法不但求解时间少于遗传算法、蚁群算法和细菌觅食算法,而且在多项评价指标上与一些代表性算法相比都具有明显的优势,能够更好地识别功能模块.
To solve the problem that the swarm intelligence clustering methods are time-consuming in detecting functional modules in protein-protein interaction networks, this paper proposes a method based on fireworks algorithm for functional module detection in protein-protein interaction networks(FWA-FMD). First, each firework individual was initialized as a candidate solution based on the label propagation idea by combining the topological and functional information. Then in each generation of evolution, each firework individual was optimized by using explosion operation with local search and global search self-adjustment capabilities, and the next generation of fireworks individuals were selected by using elite retention and roulette strategy. Finally, the nodes with the same label in the optimal firework were divided into the same function module to obtain the final function module detection result. Functional module detection results on the four protein-protein interaction network datasets of Saccharomyces cerevisiae and Homo sapiens were evaluated by using two standard functional module datasets as benchmarks, which shows that the FWA-FMD algorithm not only costs less time than GA-PPI, ACC-FMD, and BFO-FMD, but also has obvious advantages in many evaluation indicators compared with some representative algorithms, which can better identify functional modules.
To solve the problem that the swarm intelligence clustering methods are time-consuming in detecting functional modules in protein-protein interaction networks, this paper proposes a method based on fireworks algorithm for functional module detection in protein-protein interaction networks(FWA-FMD). First, each firework individual was initialized as a candidate solution based on the label propagation idea by combining the topological and functional information. Then in each generation of evolution, each firework individual was optimized by using explosion operation with local search and global search self-adjustment capabilities, and the next generation of fireworks individuals were selected by using elite retention and roulette strategy. Finally, the nodes with the same label in the optimal firework were divided into the same function module to obtain the final function module detection result. Functional module detection results on the four protein-protein interaction network datasets of Saccharomyces cerevisiae and Homo sapiens were evaluated by using two standard functional module datasets as benchmarks, which shows that the FWA-FMD algorithm not only costs less time than GA-PPI, ACC-FMD, and BFO-FMD, but also has obvious advantages in many evaluation indicators compared with some representative algorithms, which can better identify functional modules.
引文
[1]JI Junzhong, ZHANG Aidong, LIU Chunnian, et al. Survey: functional module detection from protein-protein interaction networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(2): 261. DOI:10.1109/TKDE.2012.225
[2]冀俊忠, 刘志军, 刘红欣, 等. 蛋白质相互作用网络功能模块检测的研究综述[J]. 自动化学报, 2014, 40(4): 577. DOI:10.3724/SP.J.1004.2014.00577JI Junzhong, LIU Zhijun, LIU Hongxin, et al. An overview of research on functional module detection for protein-protein interaction networks[J]. Acta Automatica Sinica, 2014(4): 577. DOI:10.3724/SP.J.1004.2014.00577
[3]BADER G D, HOGUE C W. An automated method for finding molecular complexes in large protein interaction networks[J]. BMC Bioinformatics, 2003, 4(1): 2. DOI:10.1186/1471-2105-4-2
[4]ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder: locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8): 1021. DOI:10.1093/bioinformatics/btl039
[5]RIVERA C G, VAKIL R, BADER J S. Nemo: network module identification in cytoscape[J]. BMC Bioinformatics, 2010, 11(Suppl 1): S61. DOI:10.1186/1471-2105-11-S1-S61
[6]LI Min, WANG Jianxin, CHEN Jian'er. A fast agglomerate algorithm for mining functional modules in protein interaction networks[C]//International Conference on Biomedical Engineering and Informatics. Sanya, China: IEEE, 2008: 3. DOI:10.1109/BMEI.2008.121
[7]PIZZUTI C, ROMBO S. Experimental evaluation of topological-based fitness functions to detect complexes in PPI networks[C]//Genetic and Evolutionary Computation Conference. Philadelphia, USA: ACM, 2012: 193. DOI:10.1145/2330163.2330191
[8]JI Junzhong, LIU Hongxin, ZHANG Aidong, et al. ACC-FMD: ant colony clustering for functional module detection in protein-protein interaction networks[J]. International Journal of Data Mining and Bioinformatics, 2015, 11(3): 331. DOI:10.1504/IJDMB.2015.067323
[9]YANG Cuicui, JI Junzhong, ZHANG Aidong. BFO-FMD: bacterial foraging optimization for functional module detection in protein-protein interaction networks[J]. Soft Computing, 2018, 22(10): 3395. DOI: 10.1007/s00500-017-2584-9
[10]TAN Ying, ZHU Yuanchun. Fireworks algorithm for optimization[C]//International Conference on Swarm Intelligence. Berlin, Heidelberg: Springer, 2010: 355. DOI:10.1007/978-3-642-13495-1_44
[11]GUENDOUZ M, AMINE A, HAMOU R M. A discrete modified fireworks algorithm for community detection in complex networks[J]. Applied Intelligence, 2017, 46(2): 373. DOI:10.1007/s10489-016-0840-9
[12]ZHENG S, JANECEK A, TAN Y. Enhanced fireworks algorithm[C]//IEEE Congress on Evolutionary Computation. Cancún, México: IEEE, 2013:2069. DOI:10.1109/CEC.2013.6557813
[13]GAVIN A C, ALOY P, GRANDI P, et al. Proteome survey reveals modularity of the yeast cell machinery[J]. Nature, 2006, 440(7084): 631. DOI:10.1038/nature04532
[14]KROGAN N J, CAGNEY G, YU H, et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae[J]. Nature, 2006, 440(7084): 637. DOI:10.1038/nature04670
[15]SALWINSKI L, MILLER C S, SMITH A J, et al. The database of interacting proteins: 2004 update[J]. Nucleic Acids Research, 2004, 32: D449. DOI:10.1093/nar/gkh086
[16]HERNANDEZ C, MELLA C, NAVARRO G, et al. Protein complex prediction via dense subgraphs and false positive analysis[J]. Plos One, 2017, 12(9): e0183460. DOI:10.1371/journal.pone.0183460
[17]CHERRY J M, ADLER C, BALL C, et al. SGD: saccharomyces genome database[J]. Nucleic Acids Research, 1998, 26(1): 73. DOI:10.1093/nar/26.1.73
[18]PU S, WONG J, TURNER B, et al. Up-to-date catalogues of yeast protein complexes[J]. Nucleic Acids Research, 2009, 37(3): 825. DOI:10.1093/nar/gkn1005
[19]KIKUGAWA S, NISHIKATA K, MURAKAMI K, et al. PCDq: human protein complex database with quality index which summarizes different levels of evidences of protein complexes predicted from H-Invitational protein-protein interactions integrative dataset[J]. BMC Systems Biology, 2012, 6(S2): S7. DOI:10.1186/1752-0509-6-S2-S7
[20]RUEPP A, WAEGELE B, LECHNER M, et al. CORUM: the comprehensive resource of mammalian protein complexes—2009[J]. Nucleic Acids Research, 2010, 38(1): D497. DOI:10.1093/nar/gkp914
[2]冀俊忠, 刘志军, 刘红欣, 等. 蛋白质相互作用网络功能模块检测的研究综述[J]. 自动化学报, 2014, 40(4): 577. DOI:10.3724/SP.J.1004.2014.00577JI Junzhong, LIU Zhijun, LIU Hongxin, et al. An overview of research on functional module detection for protein-protein interaction networks[J]. Acta Automatica Sinica, 2014(4): 577. DOI:10.3724/SP.J.1004.2014.00577
[3]BADER G D, HOGUE C W. An automated method for finding molecular complexes in large protein interaction networks[J]. BMC Bioinformatics, 2003, 4(1): 2. DOI:10.1186/1471-2105-4-2
[4]ADAMCSEK B, PALLA G, FARKAS I J, et al. CFinder: locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8): 1021. DOI:10.1093/bioinformatics/btl039
[5]RIVERA C G, VAKIL R, BADER J S. Nemo: network module identification in cytoscape[J]. BMC Bioinformatics, 2010, 11(Suppl 1): S61. DOI:10.1186/1471-2105-11-S1-S61
[6]LI Min, WANG Jianxin, CHEN Jian'er. A fast agglomerate algorithm for mining functional modules in protein interaction networks[C]//International Conference on Biomedical Engineering and Informatics. Sanya, China: IEEE, 2008: 3. DOI:10.1109/BMEI.2008.121
[7]PIZZUTI C, ROMBO S. Experimental evaluation of topological-based fitness functions to detect complexes in PPI networks[C]//Genetic and Evolutionary Computation Conference. Philadelphia, USA: ACM, 2012: 193. DOI:10.1145/2330163.2330191
[8]JI Junzhong, LIU Hongxin, ZHANG Aidong, et al. ACC-FMD: ant colony clustering for functional module detection in protein-protein interaction networks[J]. International Journal of Data Mining and Bioinformatics, 2015, 11(3): 331. DOI:10.1504/IJDMB.2015.067323
[9]YANG Cuicui, JI Junzhong, ZHANG Aidong. BFO-FMD: bacterial foraging optimization for functional module detection in protein-protein interaction networks[J]. Soft Computing, 2018, 22(10): 3395. DOI: 10.1007/s00500-017-2584-9
[10]TAN Ying, ZHU Yuanchun. Fireworks algorithm for optimization[C]//International Conference on Swarm Intelligence. Berlin, Heidelberg: Springer, 2010: 355. DOI:10.1007/978-3-642-13495-1_44
[11]GUENDOUZ M, AMINE A, HAMOU R M. A discrete modified fireworks algorithm for community detection in complex networks[J]. Applied Intelligence, 2017, 46(2): 373. DOI:10.1007/s10489-016-0840-9
[12]ZHENG S, JANECEK A, TAN Y. Enhanced fireworks algorithm[C]//IEEE Congress on Evolutionary Computation. Cancún, México: IEEE, 2013:2069. DOI:10.1109/CEC.2013.6557813
[13]GAVIN A C, ALOY P, GRANDI P, et al. Proteome survey reveals modularity of the yeast cell machinery[J]. Nature, 2006, 440(7084): 631. DOI:10.1038/nature04532
[14]KROGAN N J, CAGNEY G, YU H, et al. Global landscape of protein complexes in the yeast Saccharomyces cerevisiae[J]. Nature, 2006, 440(7084): 637. DOI:10.1038/nature04670
[15]SALWINSKI L, MILLER C S, SMITH A J, et al. The database of interacting proteins: 2004 update[J]. Nucleic Acids Research, 2004, 32: D449. DOI:10.1093/nar/gkh086
[16]HERNANDEZ C, MELLA C, NAVARRO G, et al. Protein complex prediction via dense subgraphs and false positive analysis[J]. Plos One, 2017, 12(9): e0183460. DOI:10.1371/journal.pone.0183460
[17]CHERRY J M, ADLER C, BALL C, et al. SGD: saccharomyces genome database[J]. Nucleic Acids Research, 1998, 26(1): 73. DOI:10.1093/nar/26.1.73
[18]PU S, WONG J, TURNER B, et al. Up-to-date catalogues of yeast protein complexes[J]. Nucleic Acids Research, 2009, 37(3): 825. DOI:10.1093/nar/gkn1005
[19]KIKUGAWA S, NISHIKATA K, MURAKAMI K, et al. PCDq: human protein complex database with quality index which summarizes different levels of evidences of protein complexes predicted from H-Invitational protein-protein interactions integrative dataset[J]. BMC Systems Biology, 2012, 6(S2): S7. DOI:10.1186/1752-0509-6-S2-S7
[20]RUEPP A, WAEGELE B, LECHNER M, et al. CORUM: the comprehensive resource of mammalian protein complexes—2009[J]. Nucleic Acids Research, 2010, 38(1): D497. DOI:10.1093/nar/gkp914