融合人工鱼群机理的PPI网络聚类模型与算法

PPI Networks Clustering Model and Algorithm Combining with the Principle of Artificial Fish School

预测蛋白质交互作用(Protein-Protein Interaction,PPI)网络中未知蛋白质的功能,是生物信息学的一个研究热点。目前基于功能流的方法能有效地解决PPI网络的聚类问题,但是其正确率偏低、时间复杂度较高。为此提出了一种融合人工鱼群机理的PPI网络聚类模型与算法:将人工鱼看作一组聚类中心,觅食行为是指从每个聚类中心开始向它的邻接结点搜索并添加结点到该聚类模块中;接下来将目标函数值最大的人工鱼对应的一组聚类模块看作初始的聚类结果,对应鱼群的追尾行为;剩下的人工鱼开始执行聚群行为,判断对应的聚类模块与初始的聚类结果之间的相似度。如果相似度低于给定的阈值,则将聚类模块添加到初始的聚类结果中。PPI数据集上的仿真实验表明,该算法可以自动确定聚类数目,而且聚类结果的正确率和算法的运行效率都优于功能流算法。

Predicting function of unknown proteins in the protein-protein interaction networks is a hot topic in the bioin- formatics. Recently functional flow method has effectively solved the problem of clustering PPI networks. However, the accuracy is relatively low and the time complexity is high. So the PPI networks clustering algorithm combining with the principle of artificial fish school was proposed, which considered an artificial fish as a set of cluster centers. The fora- ging behavior was regarded as searching the neighbor nodes of initial cluster centers and adding the nodes into cluster module. Afterwards the set of cluster modules having the highest fitness value was selected as the initial cluster result, which was corresponding to the following behavior of artificial fish school. Then other artificial fish began to execute swarming behavior and judged the similarities between the corresponding cluster modules and initial cluster result. If the similarity was lower than given threshold, the cluster module was added into the initial cluster result. The simulation ex- periment on PPI datasets shows that this algorithm can automatically determine cluster number. In addition, both the accuracy of cluster result and efficiency of algorithm are superior to functional flow algorithm.