基于文化算法的PPI网络功能模块检测方法

冀俊忠; 高光轩

doi:10.11936/bjutxb2016100034

基于文化算法的PPI网络功能模块检测方法

doi: 10.11936/bjutxb2016100034

北京工业大学信息学部多媒体与智能软件技术北京市重点实验室, 北京 100124

基金项目: 国家自然科学基金资助项目(61375059)

详细信息

作者简介:
作者简介: 冀俊忠(1969—), 男, 教授, 主要从事机器学习、人工智能方面的研究, E-mail:jjz01@bjut.edu.cn

中图分类号: Q811.4;TP301.6
计量
- 文章访问数: 83
- HTML全文浏览量: 66
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2016-10-14
- 网络出版日期: 2022-09-09
- 刊出日期: 2017-01-01

Detecting Functional Module Method Based on Cultural Algorithm in Protein-protein Interaction Networks

Beijing Municipal Key Laboratory of Multimedia and Intelligent Software, Faculty of Information Technology,Beijing University of Technology, Beijing 100124,China

摘要

摘要: 为了解决蛋白质相互作用(protein-protein interaction,PPI)网络功能模块检测问题,提出一种基于文化算法的PPI网络功能模块检测(CA-FMD)方法. 首先,每个个体采用基于节点邻居有序表的编码方式表示功能模块检测问题的一个可行解. 然后,利用文化算法的双层进化机制获得最优解,其中,上层机制用来模拟信念空间中群体经验的进化,下层机制用来刻画种群空间中个体的进化. 最后,借助2个空间的相互作用和影响完成解的优化. 在3个数据集上的实验结果表明:与其他算法相比,CA-FMD方法在多项评价指标上都具有明显的优势.
- 蛋白质相互作用网络 /
- 功能模块检测 /
- 文化算法
Abstract: To achieve function module detection in protein-protein interaction (PPI) networks, a PPI network functional module detection method based on cultural algorithm (CA-FMD) was proposed. First, an ordered adjacency list encoding scheme was used to model an individual in the population space. Then, the evolutionary mechanism of cultural algorithm was designed and employed to obtain the optimal solution, where the upper mechanism simulated the evolution of the group experience in the belief space, and the lower mechanism described the evolution of individuals in the population space. Finally, the optimation of solutions was completed by the interaction and influence of the two spaces. Experimental results on three datasets show that the CA-FMD method has obvious advantages in some evaluation metrics compared with other algorithms.
- protein-protein interaction (PPI) network /
- functional module detection /
- cultural algorithm
The authors have declared that no competing interests exist.

HTML全文

图 1 文化算法框架

Figure 1. Cultural algorithm framework

下载: 全尺寸图片幻灯片

图 2 PPI网络

Figure 2. PPI networks

下载: 全尺寸图片幻灯片

图 3 邻居有序表

Figure 3. Ordered adjacency list

下载: 全尺寸图片幻灯片

图 4 个体的编码

Figure 4. Encoding of an individual

下载: 全尺寸图片幻灯片

图 5 解码结果

Figure 5. Decoding results

下载: 全尺寸图片幻灯片

图 6 样本库示例

Figure 6. Sample library examples

下载: 全尺寸图片幻灯片

图 7 6种算法在Gavin数据集上的结果比较

Figure 7. Comparative result of six algorithms for Gavin data

下载: 全尺寸图片幻灯片

图 8 6种算法在DIPcore数据集上的结果比较

Figure 8. Comparative result of six algorithms for DIPcore data

下载: 全尺寸图片幻灯片

图 9 6种算法在MIPS数据集上的结果比较

Figure 9. Comparative result of six algorithms for MIPS data

下载: 全尺寸图片幻灯片

表 1 6种算法在Gavin数据集上的实验结果

Table 1. Experimental results of six algorithms in Gavin data sets

算法	模块数	模块平均大小	N_cp≥0.2	N_cb≥0.2
CA-FMD	157	9.11	97	169
CFinder	98	11.47	54	89
Jerarca	264	5.42	101	172
COACH	326	2.35	123	197
MCL	449	3.19	188	224
MCODE	66	9.12	49	85

下载: 导出CSV

表 2 6种算法在DIPcore数据集上的实验结果

Table 2. Experimental results of six algorithms in DIPcore data sets

算法	模块数	模块平均大小	N_cp≥0.2	N_cb≥0.2
CA-FMD	360	6.96	155	234
CFinder	169	6.94	94	148
Jerarca	578	4.34	150	230
COACH	382	2.89	136	155
MCL	1032	2.43	280	279
MCODE	85	6.15	54	95

下载: 导出CSV

表 3 6种算法在MIPS数据集上的实验结果

Table 3. Experimental results of six algorithms in MIPS data sets

算法	模块数	模块平均大小	N_cp≥0.2	N_cb≥0.2
CA-FMD	461	9.86	112	161
CFinder	178	7.79	55	86
Jerarca	1221	3.72	124	158
COACH	489	2.61	90	102
MCL	1774	2.56	258	250
MCODE	63	8.33	25	46

下载: 导出CSV

参考文献(27)

[1]	AKOADJEI D, FU W, WALLIN C, et al.HIV-1, human interaction database: current status and new features[J]. Nucleic Acids Research, 2014, 43(D1): 566-570.
[2]	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 & Data Engineering, 2014, 26(2): 261-277.
[3]	JI J Z, LIU Z J, LIU H X, et al.An overview of research on functional module detection for protein-protein interaction networks[J]. Acta Automatica Sinica, 2014, 40(4): 577-593. (in Chinese)
[4]	RAVAEE H, MASOUDI-NEJAD A, OMIDI S, et al.Improved immune genetic algorithm for clustering protein-protein interaction network[C]//IEEE International Conference on Bioinformatics and Bioengineering. Washington, DC: IEEE Computer Society, 2010: 174-179.
[5]	LEI X J, TIAN J F.The Information flow clustering model and algorithm based on the artificial bee colony mechanism of PPI networks[J]. Chinese Journal of Computers, 2012, 35(1): 134-145. (in Chinese)
[6]	JI J Z, LIU Z J, ZHANG A D, et al.ZHAM-FMD: mining functional modules in protein-protein interaction networks using ant colony optimization and multi-agent evolution[J]. Neurocomputing, 2013, 121(18): 453-469.
[7]	JI J Z, JIAO L, YANG C C, et al.MAE-FMD: multi agent evolutionary method for functional module detection in protein-protein interaction networks[J]. BMC Bioinformatics, 2014, 15(1): 325.
[8]	JI J Z, LÜ 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 & Bioinformatics, 2016, 13(4): 610-622.
[9]	REYNOLDS R G.An introduction to cultural algorithms[C]∥Proceedings of the 3rd Annual Conference on Evolutionary Programming. Singapore: World Scientific Publishing, 1994: 131-136.
[10]	MCDONNELL J, REYNOLDS R, FOGEL D.Using cultural algorithms for constraint handling in GENOCOP[M]∥Evolutionary Programming Ⅳ: Proceedings of the Fourth Annual Conference on Evolutionary Programming. San Piego, CA: MIT Press, 1995: 289-305.
[11]	HUANG H Y, GU X S, LIU M D.Research on cultural algorithm for solving nonlinear constrained optimization[J]. Acta Automatica Sinica, 2007, 33(10): 1115-1120. (in Chinese)
[12]	GUO Y N, LIU D D, CHENG J, et al.Adaptive cultural algorithm adopting mixed mutation[J]. Acta Electronica Sinica, 2011, 39(8): 1913-1918. (in Chinese)
[13]	LI M, LU F B, CHEN H.Adaptive cultural algorithm adopting mixed mutation[J]. Acta Electronica Sinica, 2015, 43(5): 888-894. (in Chinese)
[14]	SOZA C, BECERRA R L, RIFF M C, et al.Solving timetabling problems using a cultural algorithm[J]. Applied Soft Computing, 2011, 11(1): 337-344.
[15]	RIVERA D C, RICARDO L B, CARLOS A, et al.Cultural algorithms, an alternative heuristic to solve the job shop scheduling problem[J]. Engineering Optimization, 2007, 39(1): 69-85.
[16]	SRINIVASAN S, RAMAKRISHNAM S.A social intelligent system for multi-objective optimization of classification rules using cultural algorithms[J]. Computing, 2013, 95(4): 327-350.
[17]	HALDAR V, CHAKRABORTY N.Power loss minimization by optimal capacitor placement in radial distribution system using modified cultural algorithm[J]. International Transactions on Electrical Energy Systems, 2013, 25(1): 54-71.
[18]	ALI M Z, AWAD N H.A novel class of niche hybrid cultural algorithms for continuous engineering optimization[J]. Information Sciences An International Journal, 2014, 267(2): 158-190.
[19]	ALI M Z, AWAD N H, SUGANTHAN P N, et al. A novel hybrid cultural algorithms framework with trajectory-based search for global numerical optimization[J]. Information Sciences, 2016, 334/335: 219-249.
[20]	FRIEDEL C C, KRUMSEK J, ZIMMER R.Bootstrapping the interactome: unsupervised identification of protein complexes in yeast[J]. Journal of Computational Biology, 2009, 16(8): 971-987.
[21]	LI X, WU M, KWOH C K, et al.Computational approaches for detecting protein complexes from protein interaction networks: a survey[J]. BMC Genomics, 2010, 11(Suppl 1): 1-19.
[22]	BROHEE S, VAN H J.Evaluation of clustering algorithms for protein-protein interaction networks[J]. BMC Bioinformatics, 2006, 7(1): 2791-2797.
[23]	ADAMCSEK B, PALLA G, FARKAS I J, et al.CFinder: locating cliques and overlapping modules in biological networks[J]. Bioinformatics, 2006, 22(8): 1021-1023.
[24]	ALDECOA R.Jerarca: efficient analysis of complex networks using hierarchical clustering[J]. Plos One, 2010, 5(7): e11585.
[25]	MIN W, LI X, KWOH C K, et al.A core-attachment based method to detect protein complexes in PPI networks[J]. BMC Bioinformatics, 2009, 10(11): 169.
[26]	VAN D S.A cluster algorithm for graphs: INS-R0010[R]. Amsterdam: CWI, 2000: 1-40.
[27]	BADER G D, HOGUE C W.An automated method for finding molecular complexes in large protein interaction networks[J]. BMC Bioinformatics, 2003, 4(1): 1-27.