基于烟花算法的蛋白质相互作用网络功能模块检测方法

Fireworks algorithm for functional module detection in protein-protein interaction networks

摘要:

针对群智能聚类方法在蛋白质相互作用网络功能模块检测问题上运行时间长的不足,本文提出了一种基于烟花算法的蛋白质相互作用网络功能模块检测方法（Fireworks Algorithm for Functional Module Detection in Protein-protein Interaction Networks,简称FWA-FMD）.首先结合蛋白质相互作用网络的拓扑结构信息和基因本体的功能注释信息,基于标签传播思想将每个烟花个体初始化为一种候选的功能模块划分.其次在每一代进化过程中,利用具有局部搜索和全局搜索自调整能力的爆炸操作对每个烟花个体进行优化,并同时采用精英保留和轮盘赌策略选择下一代烟花个体.最后通过将最优烟花个体中标签相同的节点划分到同一功能模块,以得到最终的功能模块检测结果.在酵母菌和人类两个物种的4个公共蛋白质相互作用网络数据集上的功能模块检测结果,分别用两种标准功能模块数据集作为基准来评价的实验表明:FWA-FMD算法不但求解时间少于遗传算法、蚁群算法和细菌觅食算法,而且在多项评价指标上与一些代表性算法相比都具有明显的优势,能够更好地识别功能模块.

Abstract:

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.