随机游走模型识别蛋白质网络复合物算法

林志杰， 任 远

(上海电机学院 电子信息学院， 上海 200240)

随机游走模型识别蛋白质网络复合物算法

林志杰， 任 远

(上海电机学院 电子信息学院， 上海 200240)

识别出蛋白质复合物是理解蛋白质相互作用的重要方法。针对蛋白质网络中存在假阴性和假阳性问题，通过随机游走模型，有针对性对假阴性和假阳性数据进行有效筛选，定义HP-complex图模型来识别具有生物意义的蛋白质复合物；利用GO本体计算蛋白质复合物之间的语义相似性，最终确定蛋白质复合物。实验证明，提出的基于随机游走模型的蛋白质复合物识别算法对输入参数不敏感，算法能够识别出有效的蛋白质复合物。

蛋白质复合物; 蛋白质网络; 随机游走; GO本体

当今生物信息发展迅猛，已经开发出很多生物学方法，如小规模(低通量)方法、co_IP大规模(高通量)方法、酵母双杂交、串联亲和纯化法等。蛋白质的识别方法众多，但是在目前发现的生物蛋白质中，以人类蛋白质为例，还有近80%的蛋白质未被发现，其他生物蛋白质已经被研究、发现的更是微乎其微。

蛋白质网络越大，需要检测的蛋白质对数量也越多。若采用低通量检测方法检测蛋白质之间的相互作用，则耗费的时间、人力、物力资源也越大。但是，与低通量检测方法相比，采用高通量方法来识别蛋白质相互作用的网络数据更容易出现错误，其可靠性相对较低。这些错误分为两种[1]： 假阳性(False Positive， FP)和假阴性(False Negative, FN)。假阳性是指实验检测出两个蛋白质间存在而在真实的蛋白质网络中并不存在的相互作用；假阴性是指实验没有检测出来而真实的蛋白质网络中却存在的相互作用。文献[2]中用实验证明在用高通量实验检测出来的数据集中，这两种错误出现的概率相差很大，其中绝大部分(高达92.5%)的错误是假阴性。由此可见，应用不同的试验方法得到蛋白质相互作用数据的质量差异性较大，即便是应用相同的试验方法，不同条件、不同的实验人员得到的相互作用数据也不尽相同，所获得的数据噪声较多，存在大量的假阴性、假阳性数据。因此，非常有必要设计具有针对性、能更有效应对假阳性、假阴性数据的计算方法，来纠正数据集中的大部分假阴性、假阳性的蛋白质相互作用。

目前，主流的蛋白质复合物识别算法，主要通过识别蛋白质网络中的全联通图或极大团的方法来识别蛋白质复合物，或定义新颖的图模型结构[3]，如HP-complex识别，但是由于这些方法能够识别的蛋白质相互作用不全，而且已经构建的蛋白质相互作用网络中还存在着假阴性和假阳性的相互作用，故仅通过挖掘全联通图来识别蛋白质复合物就存在着很大的局限性。

另外，单纯地依据蛋白质-蛋白质相互作用(Protein-Protein Interaction, PPI)网络的拓扑结构特征来进行模块识别，把网络中的稠密子图(Dense Subgraph, DS)作为要找寻的蛋白质复合物或功能模块[4]，这些方法也存在一个共同的缺点[5-15]： 由于蛋白质模块中的所有蛋白质在生物系统中共同完成某种生物功能，而这些模块并非与PPI网络中的稠密子图做到一一对应，故单纯地依据拓扑结构特征来进行模块识别，会影响到后期蛋白质功能预测的精度及可信度。因此，如何在蛋白质网络拓扑结构特征的基础上，确定性地衡量网络中的稠密子图的功能意义是一个急需解决的问题。

为了解决蛋白质数据集中包含假阴性和假阳性噪声数据的问题，以及利用图模型寻找蛋白质复合物结构固定的局限性，本文研究了一个基于随机游走模型的蛋白质复合物识别算法(Find Protein Complexes Based on Random Walk with Restart, RWSPFinder)，借助于随机游走算法来预测蛋白质网络上那些真正存在的相互作用的数据，从而去除那些假阴性或假阳性的噪声数据；然后定义HP-complex图模型来识别具有生物意义的蛋白质复合物；最后，根据GO本体计算蛋白质复合物之间的语义相似性，最终确定所识别的蛋白质复合物。算法对输入参数不敏感，实验验证了提出算法的有效性。

1 蛋白质复合物识别

1.1随机游走模型

Random Walk是随机过程(Stochastic Process)的一个重要研究内容，是一种不规则的运动形式，通常描述的是最简单的一维Random Walk过程。如考虑在数轴原点处有一只蚂蚁，它自当前位置x处从t时刻出发，在下一个时刻(t+1)以1/2向前走一步，该点为

X_{t+1}=X_{t}+1

或以1/2向后退一步，该点为

X_{t+1}=X_{t}-1

这样该蚂蚁每个时刻到达的点序列就构成一个一维随机游走过程。本质上，Random Walk是一种随机化的方法，在实际生活中，如醉汉行走的轨迹、花粉的布朗运动、证券的涨跌等都与Random Walk有密不可分的关系。Random Walk已被成功地应用到数学、物理、化学、生物、经济等各领域。

1.2HP-complex图模型

给定物种的蛋白质互作网络可以视为网络图G=(V,E)，其中，V为蛋白质结点；E为蛋白质相互作用边的集合，从所有的边的集合中去掉网络中自连接边和重复边。为从蛋白质互作网络或图G中发现定义的蛋白质复合物，从而为从蛋白质网络中识别蛋白质复合物做准备，本文定义以下概念。

定义1HP-vertices结点 给定蛋白质互作网络G=(V,E)，其中，V为蛋白质互作网络的顶点；E为蛋白质互作网络的边；H-index为一个图模型，用H表示。利用HP-vertices结点代表H-index结点，定义为

其中，d(v)为网络顶点v的度；h为蛋白数。

由HP-vertices结点可扩展至概念HP-neighbors。

定义2HP-neighbors HP-neighbors定义为HP-vertices蛋白质集的一阶邻居的集合。

定义3HP*-graph图 蛋白质互作网络G的子图HP*-graph由HP-vertices和其HP-neighbors组成，除去了一阶邻HP-neighbors之间的边。

对于一个蛋白质互作网络，HP*-graph从一个很大的原始蛋白质互作网络里分离出来，有可能是一个非连通子图。因此，从非连通子图HP*-graph中分离出所有的子图、最终得到的蛋白质互作网络的所有子图为要识别的蛋白质复合物。

定义4HP-complex复合物 如果HP*-graph是非连通的，HP-complex定义为HP*-graph的所有子图，故HP*-graph中分离的子图都是要找的蛋白质复合物。

2 蛋白质复合物相似性计算

2.1GO的结构

基因本体GO有3个主要用途[16]： ① 指定可控制的结构化词汇库(即本体)，用来描述分子生物学的重点领域，包括基因产物特性和生物序列，为杂乱无章的生物概念和词汇定义统一的概念称谓、定义和概念之间的关系；② 应用基因本体GO来注释生物数据库中的序列、基因以及基因产物；③ 应用基因本体GO提供一个公共资源，让人们方便使用GO本体，注释数据集和GO软件工具。基因本体论GO的定义法则使得目前很多合作的数据库的生物信息查询具有很好的一致性，而基因本体论中的定义语言具有多重结构，故其能在各种程度上支持生物信息查询。

2.2基于随机游走的蛋白质复合物算法

本文研究的RWSPFinder算法经过2次蛋白质相互作用数据的假阳性过滤： 第1次是对整个加权的蛋白质互作网络进行重启型的随机游走，重构蛋白质互作网络；然后，对重构的蛋白质互作网络进行初始的蛋白质复合物识别。第2次是在找到的初始蛋白质复合物内部执行基于基因本体GO语义相似性的蛋白质相互作用假阳性过滤。

RWSPFinder算法的输入、输出伪代码如下：

1. Input： PPIG(V,E,W); Gene Ontology tool; G-sesame; Rank threshold of Protein node; Similarity thresholdPs

2. Output： the Protein Complexes Set PC

3. Initializep0for Random Walk and the PC=Null that means the set of Protein Complexes is Null

4. Random Walk with Restart on Weighted PPI until pt to stable state

5. Obtaining the important proteins according to the threshold Pr from original PPI; Constructing the new PPI network

6. Executing the Algorithm HPCMiner on new PPI network to mining the initial Protein Complexes Set

若2个蛋白质之间的相似性越大，表示它们之间发生或具有相互作用的可能性越大；反之，则表示它们之间发生或具有相互作用的可能性也越小。本文通过设定GO语义相似性阈值，衡量蛋白质复合物内部相互作用的存在合理性。如果蛋白质之间的语义相似度大于指定阈值，则认为蛋白质之间相互作用存在合理，便保留在蛋白质复合物的内部；反之，则认为蛋白质之间不会发生相互作用，即被认定为假阳性过滤出蛋白质复合物。

3 实验结果与分析

本文利用Graphweb工具，它是一个公共的基于图分析数据的生物网络Web服务器，也是一个生物网络图数据分析工具；该生物工具可以分析包括基因、蛋白质和基因表达微阵列数据等有向和无向生物网络、加权网络、无权网络生物数据集[17]。实验中，将4个生物蛋白质相互作用数据集进行处理，得到GraphWeb可以识别的规定的数据格式；然后，利用该实验工具，分别上传4个生物蛋白质互作网络数据集，包括Human、Mouse、Rat和Yeast，得到每个蛋白质互作网络的结点(Nodes)、边(Edges)、边密度(Edge Density, ED)和结点的平均度密度(Average Node Degree, AveD)信息，来了解和认识这些生物网络的特征。

目前，在生物信息学中蛋白质复合物或蛋白质模块识别已经成为生物领域的研究热点和难点问题。关于识别出的复合物结果的评价标准也有很多，具有代表意义的评价标准有F-measure、共位置值、GO语义相似性、功能显著性(富集分析)[18]。其中，功能显著性是在GO语义丰度基础上提出的一种新的用来衡量蛋白质复合物或模块集的标准[19]。本文主要采用F-measure以及功能显著性即GO富集分析的方法来评测本文找到的蛋白质复合物具有的生物学意义。

本文提出的RWSPFinder算法对4个蛋白质互作网络数据集Yeast、Human、Mouse、Rat进行蛋白质复合物识别，最终得到蛋白质网络的蛋白质复合物数量分别是377、1646、344、65个。

为了清晰地表达蛋白质复合物的识别结果，用RWSPFinder算法识别出的蛋白质网络的复合物数量分为4组，当蛋白质复合物中包含的蛋白质复合物数Pn≥100时，该蛋白质复合物为A组；当50≤Pn<100时，该蛋白质复合物为B组；当30≤Pn<50时，该蛋白质复合物为C组；当2≤Pn<30时，该蛋白质复合物为D组。统计结果如表1所示。

表1 在4个蛋白质网络上RWSPFinder识别的蛋白质复合物的信息Tab.1 Protein complex identified by the algorithm for protein-protein interaction network on four PPIs

由表1可见，酵母蛋白质网络中仅有几个很大的簇，约有96.02%的蛋白质复合物包含的蛋白质个数小于30，表明通过RWSPFinder算法得到的蛋白质复合物的大小在2～30的正常范围内。在Human数据集中，所有寻找到的蛋白质复合物中包含的蛋白质有97.93%都小于30个；在Mouse数据集上，所有寻找到的蛋白质复合物中包含的蛋白质有98.84%都小于30个。而在Rat数据上，该比率竟然几乎达到100%。

实验结果表明，基于随机游走模型以及GO本体过滤假阳性数据的蛋白质复合物识别方法是非常有效的，能够找到具有生物意义的蛋白质复合物。

4 结 语

本文研究了一种新的蛋白质复合物识别算法。该算法致力于提高当前蛋白质网络数据质量，去掉由于高通量生物实验获得的蛋白质相互作用数据集存在的假阴性、假阳性数据，从而提高了蛋白质复合物识别的准确性和有效性。该方法利用真实的蛋白质相互作用数据集进行实验验证，通过识别到的蛋白质复合物的实验结果表明，基于随机游走模型的蛋白质复合物识别算法能够去掉蛋白质网络上的假阳性、假阴性的相互作用数据，是一个非常实用和有效的蛋白质复合物识别模型。

[1] Ovaska K,Laakso M,Hautaniemi S.Fast gene ontology based clustering for microarray experiments[J].BioData Mining,2008(1): 11.

[2] Du Zhidian,Li Lin,Chen Chinfu,et al.G-SESAME： Web tools for Go-term-based gene similarity analysis and knowledge discovery[J].Nucleic Acids Research,2009,37: W345-W349.

[3] Gibbons F D,Roth F P.Judging the quality of gene expression-based clustering methods using gene annotation[J].Genome Research,2002,12(10)： 1574-1581.

[4] Yu Liang,Gao Lin,Kong Chuiliang.Identification of core-attachment complexes based on mining maximal frequent patterns in proteinprotein interaction networks.[C]∥2010 IEEE International Conference on Bioinformatics and Biomedicine Workshops. HongKong: IEEE,2010: 29-34.

[5] Wang Jianxin,Lin Binbin,Li Min,et al.Identifying protein complexes from interaction networks based on clique percolation and distance restriction[J].BMC Genomics,2010,11(suppl2): s10.

[6] Zheng Guangyong,Wang Haibo,Wei Chaochun,et al.iGepros： An integrated gene and protein annotation server for biological nature exploration[J]. BMC Bioinformatics,2011,12(Suppl14)： S6.

[7] Lacruz R S，Brookes S J，Wen Xin，et al.Adaptor protein complex 2-mediated,clathrin-dependent endocytosis,and related gene activities,are a prominent feature during maturation stage amelogen[J]. Journal of Bone and Mineral Research，2013,28(3): 672-687.

[8] Cousins S L,Innocent N,Stephenson F A.Netol associates with the NMDA receptor/amyloid precursor protein complex[J].Journal of Neurochemistry,2013,126(5): 554-564.

[9] Piwowara M,Banacha M,Koniecznyb L.Irena Roterman Hydrophobic core formation in protein complex of cathepsin[J].Journal of Biomolecular Structure and Dynamics,2014,32(7): 623-634.

[10] OlzhausenJ,Moritz T,Neetz T,et al.Molecular characterization of the heteromeric coenzyme asynthesizing protein complex(CoA-SPC) in the yeast Saccharomyces cerevisiae[J]. FEMS Yeast Research,2013，13(6)： 565-573.

[11] Lee N P,Mruk D D,Conway A M,et al.Zyxin,axin,and Wiskott-Aldrich syndrome protein are adaptors that link the cadherin/catenin protein complex to the cytoskeleton at adherens junctions in the seminiferous epithelium of the rat testis[J]. Journal of Andrology,2004,25(2): 200-215.

[12] Alegrel E,Rebmann V,Lemaoult J,et al. In vivo identification of an HLA-G complex as ubiquitinated protein circulating in exosomes[J]. European Journal of Immunology,2013,43(7): 1933-1939.

[13] Foerster S,Kacprowski T,Dhople M V,et al.Characterization of the EGFR interactome reveals associated protein complex networks and intracellular receptor dynamics[J].PROTEOMICS,2013,13(21): 3131-3144.

[14] Whitworth K,Bradford M K,Camara N， et al.Targeted disruption of an EH-domain protein endocytic complex,Pan1-End3[J].Traffic,2014,15(1): 43-59.

[15] Brenner D A.Fra,Fra away： The complex role of activator protein 1 in liver injury[J].Hepatology,2014,59(1): 19-20.

[16] Ashburner M,Ball C A,Blake J A,et al.Gene ontology： tool for the unification of biology[J].Nature Genet,2000,25： 25-29.

[17] Reimand J,Tooming L,Peterson H,et al.GraphWeb： mining heterogeneous biological networks for gene modules with functional significance[J].Nucleic Acids Research,2008,36： W452-W459.

[18] King A D,Przulj N,Jurisica I. Protein complex prediction via cost-based clustering[J]. Bioinformatics,2004,20(17)： 3013-3020.

[19] Altaf-UI-Amin M,Shinbo Y,Mihara K,et al.Development and implementation of an algorithm for detection of protein complexes in large interaction networks[J]. BMC Bioinformatics,2006,7： 207.

Algorithm of Protein Complex Identification Using Random Walk Model

LINZhijie，RENYuan

(School of Electronic Information Engineering, Shanghai Dianji University,Shanghai 200240, China)

Protein complex identification is important in understanding the protein-protein interaction. This paper solves the problem of false positive and false negative in protein networks. A random walk model is used for effective screening false positive and false negative in the filtered data. With relatively clean protein networks, the definition of HP-complex graph model is given to identify protein complexes with biological meaning and semantic. GO ontology is used between calculated protein complex similarities, and the protein complexes are ultimately determined. Experiments show that the proposed algorithm for is insensitive to the input parameters. The algorithm can effectively identify protein complex.

protein complex; protein-protein interaction network; random walk; gene ontology

2014 - 10 - 08

林志杰(1980-)，女，讲师，博士，主要研究方向为数据挖掘，E-mail: linzj@sdu.edu.cn

2095 - 0020(2014)06 -0347 - 05

TP 301.6

A