徐周波 ，杨 健 ，刘华东 ，2*，黄文文

（1.广西可信软件重点实验室（桂林电子科技大学），广西桂林541004； 2.桂林电子科技大学机电工程学院，广西桂林541004）

（∗通信作者电子邮箱yj18677311628@163.com）

0 引言

蛋白质是构成生命体的关键成分，是细胞中大多数生物过程的重要参与者。由于蛋白质很少以独立个体的方式实现生物功能，即在一个细胞的生物过程中所涉及的蛋白质一般以蛋白质复合物等形式来实现特定的生物功能。识别、预测生物体中的蛋白质复合物对研究生物进程有着重要意义。如何通过计算的方法快速、有效地识别具有生物学功能的复合物成为一项关键的科学问题。

蛋白质相互作用（Protein-Protein Interaction，PPI）［1］网络通常由图的模型来表示，蛋白质复合物可认为是PPI网络中的一个稠密子图。van Dongen［2］通过随机游走的方法提出了蛋白质复合物检测的马尔可夫聚类（Markov CLustering，MCL）算法，MCL算法具有较强的鲁棒性，能够适应网络变化，但是准确性较低，且无法识别重叠簇。Bader等［3］提出的分子复合物检测（Molecular COmplex DEtection，MCODE）算法通过对顶点赋值并选取种子节点，迭代地从种子节点向外扩张加入新节点，最终形成簇，MCODE算法可以产生有重叠的簇，但产生簇的个数较少，使得某些复合物包含的蛋白质数量过大。Nepusz等［4］提出了基于重叠邻居的扩展聚类（Cluster with Overlapping Neighborhood Expansion，ClusterONE）方法，该算法可以有效检测PPI网络中重叠的蛋白质复合物，但算法精准度及敏感度较低。Liu等［5］提出了基于极大团的聚类方法（Clustering based on Maximal Clique，CMC），该算法运用极大团理论从PPI网络中挖掘蛋白质复合物，CMC算法提高了预测的准确性，但对小规模复合物检测效果较差，敏感度较低。……