基于图嵌入与拓扑结构信息的蛋白质复合物识别算法*

徐周波，李 萍，刘华东，李 珍

(桂林电子科技大学广西可信软件重点实验室，广西 桂林 541004)

1 引言

蛋白质复合物作为大分子组装体，在细胞稳态、生长和增殖所必需的多种生化活动中发挥着重要作用[1]。蛋白质复合物是生化体制和细胞结构的研究基础，因此，蛋白质复合物的识别成为近年来的研究热点。

目前蛋白质复合物识别技术主要分为2类:(1)基于实验的蛋白质复合物识别技术；(2) 基于计算方法的蛋白质复合物识别技术。基于实验的蛋白质复合物识别技术主要根据实验结果识别蛋白质复合物，如免疫共沉淀[2,3]和双杂交系统[4,5]，但其通常耗时较长且需高水平的专业知识作为基础。为克服基于实验的蛋白质复合物识别技术的缺点，研究者们提出了多种基于计算方法的蛋白质复合物识别技术。基于计算方法的蛋白质复合物识别技术的基本思想是从蛋白质相互作用PPI(Protein-Protein Interaction) 网络中识别呈现蛋白质复合物某些典型特性的簇。因此，PPI网络通常建模为图的形式，其中图的节点表示蛋白质，边表示蛋白质间的相互作用。蛋白质复合物的识别问题可以归结为一个传统的图聚类问题，由此产生的子图聚类被视为感兴趣的蛋白质复合物。Nepusz等[6]提出了聚类算法ClusterONE用于从PPI网络中发现重叠蛋白质复合物。ClusterONE可有效识别重叠蛋白质复合物，并采用最大匹配率MMR(Maximum Matching Rate)来评估算法的复杂度，该算法精准度和敏感度较低。Liu等[7]提出了一种基于最大团的聚类算法CMC (Clustering-based on Maximal Cliques)，利用最大团簇从加权PPI网络中发现复合群。……