基于蜂群和广度优先遍历的PPI网络聚类

PPI Network Clustering Based on Artificial Bee Colony and Breadth First Traverse Algorithm

蛋白质交互作用(PPI)网络聚类算法是研究和揭示蛋白质功能的主要方法之一.由于PPI网络的特性,传统算法不能有效聚类.文中提出一种基于蜂群和广度优先遍历的聚类算法.为避免噪声点对实验结果的干扰,在预处理阶段利用距离-密度算法确定聚类个数,剔除噪声点.然后利用结点网络综合特征值确定初始聚类中心,利用广度优先遍历搜索算法进行聚类.再采用改进的蜂群算法自动寻找最优合并阈值.最后用正确率和查全率对该算法进行性能评价并对算法中一些重要参数进行仿真分析,仿真结果表明该聚类算法有效提高PPI网络的聚类效果.

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 （BFF） 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 BNF 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.