|
|
|
| PPI Network Clustering Based on Artificial Bee Colony and Breadth First Traverse Algorithm |
| TIAN Jian-Fang, LEI Xiu-Juan |
| School of Computer Science,Shaanxi Normal University,Xi’an 710062 |
|
|
|
|
Abstract The clustering of protein-protein interaction (PPI) network is one of the principal methods to reveal and research the protein function.The traditional clustering methods are inefficient for PPI network due to its special characters. Therefore, a clustering method is proposed based on the optimal search of artificial bee colony (ABC) algorithm and the breadth first traverse (BFT) clustering algorithm. To avoid noisy interference on experimental results, the distance-density algorithm is used to roughly determine the number of clustering in the preprocessing stage. Then, the initial clustering center is determined based on the comprehensive feature value of nodes in the network. The BFT algorithm is used in the clustering process and the improved ABC algorithm is employed to automatically search the optimal merging threshold. Finally, the performance of the proposed algorithm is estimated by precision and recall and some key parameters of the algorithm is analyzed. The experimental results show that the proposed algorithm improves the clustering effect of the PPI network efficiently.
|
|
Received: 09 December 2010
|
|
|
|
|
|
[1] Zhang Aidong.Protein Interaction Networks.Cambridge,UK: Cambridge University Press,2009
[2] Schwikowski B,Uetz P,Fields S.A Network of Protein-Protein Interactions in Yeast.Nature Biotechnology,2000,18(12): 1257-1261
[3] Alexander W R,Timothy G.Modular Organization of Cellular Networks.Proc of the National Academy of Science of the USA,2003,100(3): 1128-1133
[4] Bu D,Zhao Y,Cai L,et al.Topological Structure Analysis of the
Protein-Protein Interaction Network in Budding Yeast.Nucleic Acids Research,2003,31 (9): 2443-2450
[5] Brun C,Chevenet F,Martin D,et al.Functional Classification of Proteins for the Prediction of Cellular Function from a Protein-Protein Interaction Network.Genome Biology,2004,5(1): R6
[6] Bader G D,Betel D,Hogue C W.BIND: The Bimolecular Interaction Network Database.Nucleic Acids Research,2003,31(1): 242-245
[7] Tornow S,Mewes H W.Functional Modules by Relating Protein Interaction Networks and Gene Expression.Nucleic Acids Research,2003,31(21): 6283-6289
[8] Nabieva E,Jim K,Agarwal A,et al.Whole-Proteome Prediction of Protein Function via Graph-Theoretic Analysis of Interaction Maps.Bioinformatics,2005,21(z1): 302-310
[9] Cho Y R,Hwang W,Ramanathan M,et al.Semantic Integration to Identify Overlapping Functional Modules in Protein Interaction Networks.BMC Bioinformatics,2007,8: 265
[10] Cho Y R,Hwang W,Zhang Aidong.Optimizing Flow-Based Modularization by Iterative Centroid Search in Protein Interaction Networks // Proc of the 7th IEEE International Conference on Bioinformatics and Bioengineering.Boston,USA,2007: 342-349
[11] Dunn R,Dudbridge F,Sanderson C M.The Use of Edge-Betweenness Clustering to Investigate Biological Function in Protein Interaction Networks.BMC Bioinformation,2005,6(1): 39
[12] Lei Xiujuan,Xu Huang,Zhang Aidong.Improved Artificial Bee Colony Algorithm and Its Application in Gene and PPI Data Clustering // Proc of the 5th IEEE International Conference on Bio-Inspired Computing: Theories and Applications.Changsha,China,2010: 514-521
[13] Mo Chunling.The Research of Clustering Methods and Community Structure in Complex Networks.Master Dissertation.Wuhan,China: Wuhan University of Technology,2007 (in Chinese)
(莫春玲.复杂网络中聚类方法及社团结构的研究.硕士学位论文.武汉:武汉理工大学,2007)
[14] Yan Weimin,Wu Weimin.Data Structure (C Language Edition).Beijing,China: Tsinghua University Press,2007 (in Chinese)
(严蔚敏,吴伟民.数据结构(C语言版).北京:清华大学出版社,2007)
[15] Karaboga D,Akay B.A Comparative Study of Artificial Bee Colony Algorithm.Applied Mathematics and Computation,2009,214(1): 108-132
[16] Ma Ruifu.Clustering Analyses Algorithm Based on the Complexity of the Networks Performance Evaluation for the Research and Application.Master Dissertation.Beijing,China: Beijing University of Technology,2009 (in Chinese)
(马瑞复.基于聚类分析算法的复杂网络绩效评估算法的研究与应用.硕士学位论文.北京:北京工业大学,2009)
[17] Barabasi A L,Albert R.Emergence of Scaling in Random Networks.Science,1999,286(5439): 509-512
[18] Lu Hongchao.The Research of Gene Function Based on Protein Network Clustering.Ph.D Dissertation.Beijing,China: Institute of Computing Technology in Chinese Academy of Sciences,2006 (in Chinese)
(卢宏超.基于蛋白网络聚类的基因功能研究.博士学位论文.北京:中国科学院计算技术研究所,2006)
[19] Tian Ye,Liu Dayou,Yang Bo.The Application of Complex Network Clustering Algorithm in Biological Network.Journal of Frontiers of Computer Science and Technology,2010,4(4): 330-337 (in Chinese)
(田 野,刘大有,杨 博.复杂网络聚类算法在生物网络中的应用.计算机科学与探索,2010,4(4): 330-337)
[20] Watts D J,Strogatz S H.Collective Dynamics of Small-World Network.Nature,1998,393(6684): 440-442
[21] Zhang Qun,Lei Xiujuan,Xu Huang,et al.An Improved Projection Pursuit Clustering Model and Its Application Based on Quantum-Behaved PSO // Proc of the 6th International Conference on Natural Computation.Yantai,China,2010,V: 2581-2585
[22] Seeley T D.The Wisdom of the Hive: The Social Physiology of Honey Bee Colonies.Boston,USA: Harvard University Press,1995
[23] Teodorovic D,Lucic P,Goran M,et al.Bee Colony Optimization: Principles and Applications // Proc of the 8th Seminar on Neural Network Applications in Electrical Engineering.Belgrade,Serbia,2006: 151-156
[24] Basturk B,Karaboga D.An Artificial Bee Colony (ABC) Algorithm for Numeric Function Optimization // Proc of the IEEE Swarm Intelligence Symposium Indianapolis.Indianapols,USA ,2006: 651-656
[25] Güldener U,Munsterkotter M,Kastenmuller G,et al.CYGD: The Comprehensive Yeast Genome Database.Nucleic Acids Research,2005,33: 364-368
[26] Kennedy J,Eberhart R C.Particle Swarm Optimization // Proc of the IEEE International Conference on Neural Networks.Perth,Australia,1995: 1942-1948
[27] Sun Jun,Feng Bin,Xu Wenbo.Particle Swarm Optimization with Particles Having Quantum Behavior // Proc of the IEEE Congress on Evolutionary Computation.San Diego,USA,2004,I: 325-331
[28] Eberhart R C,Shi Yuhui.Tracking and Optimizing Dynamic Systems with Particle Swarms // Proc of the IEEE Congress on Evolutionary Computation.Seoul,Korea,2001,Ⅰ: 94-100
[29] Lei Xiujuan,Fu Ali.2-D Maximum-Entropy Thresholding Image Segmentation Method Based on Second-Order Oscillating PSO // Proc of the 5th International Congress on Natural Computation.Tianjin,China,2009,III: 161-165
[30] Ma Qianzhi,Lei Xiujuan.The Application of Hybrid Orthogonal Particle Swarm Optimization in Robotic Path Planning // Proc of the 6th International Conference on Natural Computation.Yantai,China,2010,VII: 3536-3540
[31] Xu Xiaojun,Lei Xiujuan,Guo Ling.Multiple Sequence Alignment Based on SWGPSO Algorithm.Computer Engineering,2011,37(6): 184-186 (in Chinese)
(徐小俊,雷秀娟,郭 玲.基于SWGPSO算法的多序列比对.计算机工程,2011,37(6): 184-186) |
|
|
|
2012, Vol. 25 
