局部路径相似度的蛋白质链接预测

王金哲， 王远威， 王红梅

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

0 引 言

链接预测旨在通过基于现有的网络拓扑信息，预测网络中缺失或者可能存在的交互关系[1]。链接预测是一种典型的复杂网络分析应用。在蛋白质交互网络中，预测蛋白质之间的相互作用对于理解蛋白质交互网络本身和其拓扑结构均有重要的意义[2]。

近年来，国内外学者在蛋白质交互网络(Protein-Protein Interaction Network, PPI)的链接预测方面做了大量的工作。现有的链接预测方法通常是利用节点局部信息进行预测。作为经典的链接预测方法，基于局部信息相似性的方法由于具有准确性高和复杂性低的特性，已应用于蛋白质交互网络中的链接预测。

基于局部信息相似性的方法通常都会基于节点间相似程度越高，链接出现的可能性越高这一假设来进行链接预测[3]。

经典的局部相似性方法有共同邻居(Common Nneighbors, CN)[4]、Adamic-Adar(AA)[5]、资源分配(Resource Allocation， RA)[6]和偏好连接(Preferential Attachment， PA)[7]等。Saito等[8]提出基于节点及其邻居节点的拓扑关系来预测蛋白质交互出现的可能性。这些经典的链接预测方法大多利用节点的共同邻居信息，而没有考虑到蛋白质社区结构信息对链接预测的贡献。

蛋白质之间的交互通常依赖生物过程的内部机制[9]。蛋白质社区通常会共同完成某一种或若干种生物学功能。在预测PPI网络的潜在交互信息时，需要结合蛋白质所在的社区结构信息来进行蛋白质交互预测。

基于上述理论，近年来有诸多学者提出了基于社区结构信息的蛋白质交互预测方法。洪海燕等[10]将PPI网络看作一个有权无向图，提出了一种基于空间关系映射的蛋白质相互作用预测方法;Sun等[11]基于群落结构和节点度的关系，提出了一种局部亲和力结构(LAS)的相似度计算方法;基于节点链接与所属社区紧密程度有关这一假设,Li等[12]提出了一种基于社区关系强度的链接预测方法。上述方法更注重挖掘网络拓扑结构，缺乏对蛋白质本身拓扑信息的挖掘。因此，在考虑到基于局部信息相似性的方法和社区结构的蛋白质交互预测方法存在的不足，文中提出了一种融合社区结构和节点度的局部路径相似度的蛋白质链接预测方法(PIPM)，在考虑蛋白质交互网络社区信息的同时，结合蛋白质之间的拓扑结构进行链接预测。

1 相关理论

1.1 社区发现

Infomap方法是M Rosvall等[13]提出的，它是思路比较特别且准确率较高的一种方法。该方法从信息论方面出发，通过双层编码方法将社区发现与信息编码结合到一起。通过量化编码长度，找到长度最短的社区划分，即找到一个好的社区划分。Infomap方法的迭代过程如下:

输入：网络G的链接集合；

输出：网络G的社区结构。

1)初始化，将网络中每个节点视为一个社区；

2)将网络中的节点随机选取出一个序列，按顺序将每个节点赋给邻居节点所在的社区，取平均比特下降最大时的社区赋给该节点，如果没有下降，则该点的社区不变；

3)重复2)直到平均每步编码长度不再变化；

4)得到网络G的社区结构。

1.2 相似度方法

现有的基于相似度的链接预测方法由于计算复杂度低，得到了较广泛的应用。CN、AA、RA、Jaccard、 PA及基于节点间路径指数的Katz和局部路径指数(Local Path， LP)是七种经典的链接预测方法,见表1。

表1 七种经典链接预测方法简介表

2 融合社区结构和节点度的局部路径相似度的蛋白质链接预测方法

社区结构信息可以为链接预测提供重要信息[17]。考虑到传统链接预测方法存在的不足，结合蛋白质交互网络的特点及复杂网络的社区结构特性，提出一种融合社区结构和节点度的局部路径相似度的蛋白质链接预测方法，预测蛋白质与蛋白质之间交互作用。主要分为四步：

1) 利用Infomap方法将网络中节点划分成多个社区;

2) 计算每个社区的紧密度指标;

3)计算基于节点度的局部路径相似度(Localpathsimilaritybasedonnodedegree，DLP);

4)结合社区紧密度指标和DLP，共同预测蛋白质交互网络中的潜在链接。

2.1 基于Infomap的社区发现方法

示例网络图如图1所示。

根据1.1介绍的Infomap方法，首先将示例网络(见图1(a))进行社区划分，社区发现的结果见图1(b) ，示例网络被分成两个社区A和B。

2.2 社区紧密度

在进行计算社区紧密度之前，首先删除比例为δ的链接作为测试集，在3.4的实验中，将δ分别取为5%、10%和20%。在本节删除10%的示例网络已有链接作为演示，假如删除的链接为1-5和9-10，得到的测试网络如图2所示。

我们注意到这样一个事实：位于同一社区内节点间的关系通常会更紧密。因此，定义一个社区紧密度，计算社区内节点之间的平均最短路径，用它来衡量社区的紧密度。图2删除测试集的示例中，A社区的平均最短路径为1.7，B社区的平均最短路径为1.3，可以发现，B社区比A社区内节点联系更紧密。也就是说社区的平均最短路径越小，社区内节点之间的链接愈紧密，即社区紧密度与社区平均最短路径成反比。

2.3 基于节点度的局部路径相似度

蛋白质交互网络中联系比较稀疏，节点之间具有的共同邻居也相对较少。为了解决传统链接预测方法，仅考虑共同邻居信息的不足，文中方法引入节点间次级邻居信息[16]，将节点间共同邻居、次级邻居与节点自身的度相结合，共同预测蛋白质网络中潜在链接的概率。

示例网络中A社区结构如图3所示。

分析示例网络1-3(节点1与节点3之间的链接)和节点1-5存在链接的概率大小来说明文中方法的有效性。在图3中，1-3和1-5的共同邻居都是2个。若仅利用共同邻居进行链接预测，则1-3和1-5产生链接的概率相同，但从示例网络中可以明显看出，1-5链接的可能性高于1-3，即仅利用节点间的共同邻居估计两节点链接的概率是不准确的。因此，在共同邻居的基础上，挖掘次级邻居对节点间链接可能性的贡献。事实上，网络中节点4作为节点1的次级邻居对于1-5的链接有着积极贡献。与此同时，假设节点间的链接概率与目标节点本身的度呈反比关系，即目标节点的度越大，节点间链接的概率越小。

考虑到次级邻居和目标节点度对最终链接产生的影响，文中定义一个基于节点度的局部路径相似度DLP，具体如下

式中：ka----节点a的度；

kb----节点b的度；

M----网络的邻接矩阵。

文中方法旨在通过结合社区紧密度和基于节点度的局部路径相似度两个主要方面预测网络中节点间的相似度，具体定义如下

式中：λa----节点a所在社区的平均最短路径;

1/λa----节点a所在社区的紧密度定义。

文中方法在图2的示例网络上进行验证，图2存在49对没有链接的节点对，实验结果中，相似度最高的五对节点对见表2。

表2 示例网络的预测结果Top5

表1中加黑字体标注的是删除的节点对，在49对没有链接的节点对中，删除的9-10和1-5节点对的相似度排在前四的位置上，表明了本方法的有效性。

2.4 方法流程

提出一种融合社区结构和节点度的局部路径相似度的蛋白质链接预测方法，PIPM方法具体步骤为：

输入：网络G的链接集合；

输出：未链接节点间的相似性分数。

1)使用社区发现方法Infomap，将网络划分成多个社区；

2)根据上一步所划分的社区结构，计算社区紧密度；

3)计算基于节点度的局部路径相似度DLP；

4)结合社区紧密度和DLP计算未连接节点间的相似度分数。

3 实验与分析

3.1 实验环境

为说明文中方法的有效性，使用Python实现了PIPM方法以及七种对比方法。使用的电脑配置为：处理器 3.3 GHz Intel Core i7，内存16 GB 1 867 MHz DDR3。实验数据集是酵母蛋白质交互网络(PPI)。实验次数为20次。

3.2 数据集

实验使用文献[18]中的核心数据集作为实验数据集，进行蛋白质交互网络上的链接预测。该数据集有1 647个蛋白质(节点)，2 518对相互作用(链接)。同时，将网络中的链接随机划分为训练集和测试集。

3.3 评价指标

为了从整体上衡量文中方法的精确度，使用AUC(Ares Under receiver operating characteristic Curve)评价指标[19]，它是衡量链接预测方法有效性的常用指标，AUC值在0与1之间，越接近1，表示预测效果越好。实验中，独立进行n次比较，每次在测试集中随机选择一条边l1，在实际不存在的边中随机选择一条边l2，如果其中l1的相似度分数高于l2有n′次，l1的相似度分数等于l2有n″次，则AUC值可以通过下式计算

3.4 实验结果与分析

在文中数据集上，每种方法进行20次独立实验，然后计算其平均值。各方法的AUC结果如图4所示。

测试集分别为5%、10%和20%，得到了上述结果。实验结果采用柱状图表示。显然，文中方法在酵母蛋白质交互网络获得了最好的实验结果。通过实验结果发现，PIPM方法在蛋白质交互网络上都优于其他方法。

4 结 语

提出一种融合社区结构和节点度的局部路径相似度的蛋白质链接预测方法，旨在通过分析蛋白质交互网络的结构特点，同时结合社区结构和基于节点度的局部路径相似度来共同预测蛋白质交互网络中潜在的链接。在真实的蛋白质交互网络进行试验，表明预测节点间的缺失链接具有显著效果，并且在不增加复杂性的情况下，比现有的经典方法在各种真实网络上表现更好。下一步工作拟将文献[20]中的深度学习方法与链接预测相结合，进一步提高链接预测的准确率。