0 引言

蛋白质作为构筑生命体的基石，几乎执行和调控着所有的生命活动，如繁殖、遗传、新陈代谢和信号传导等。众所周知，蛋白质被赋予的功能，不是通过单独个体完成的，而是通过蛋白质间的相互作用、共同调控才完成的。在一个生命有机体内，所有蛋白质通过相互作用组成的网络简称蛋白质相互作用网络^[1]。在PPIN中，通过相互作用共同完成某一特定生命活动的蛋白质集合称为一个功能模块。生命科学的研究表明，对蛋白质功能模块的预测不但有助于对未知功能的蛋白质进行功能探索^[2]，而且对疾病的诊断和药物的开发具有重要意义^[3]。因此，高质量的预测蛋白质功能模块是后基因时代亟待解决的重要问题之一。

传统的PPIN功能模块检测是通过生物试验的方法进行的，但该方法在检测质量、检测费用和时间开销等方面存在局限性。而近些年，随着蛋白质组学的发展，尤其是随着高通量技术的发展，人们获得了大量的蛋白质相互作用数据^[4]。显然，仅通过生物试验的传统方法进行PPIN功能模块检测已经跟不上时代的步伐。而以机器学习为基础的计算方法因周期短、开销少等优点迅速成为该领域中的一个研究热点，一系列基于计算的方法在该领域中相继涌现^[5]。例如：文献[6]提出基于密度的检测算法MCODE，它首先通过局部邻域密度，选择初始的种子节点，然后以种子节点为中心，不断地向外扩展，最后完成功能模块的划分。虽然该算法能够完成聚类功能，但不能很好地对存在很多稀疏节点的网络进行聚类。文献[7]提出一种基于层次的聚类算法jerarca，该方法首先计算蛋白质网络的距离矩阵，接着根据距离矩阵建立该网络的层次树，最后根据模块内、模块间的连接分布进行最优的模块划分。文献[8]提出一种基于核心附属关系的coach算法。该方法首先发现核心蛋白质，然后逐个地把附属蛋白质归置到核心蛋白质所属的模块。文献[9]设计了在PPIN中探测功能模块的cfinder软件, 其特点是能够识别重叠的模块，但选择合理的参数十分困难，常导致聚类时漏掉一些模块。文献[10]提出基于马尔科夫的聚类算法MCL，该算法是流模拟方法中的一种，它通过扩充和膨胀两种操作来完成对聚类模块的挖掘。该算法能够克服数据中的噪声，具有很强的鲁棒性。近年来，随着群集智能思想的快速发展，很多学者把群智能的方法应用到PPIN功能模块检测中，并取得了不错的效果。例如，文献[11]结合PPIN的拓扑特征，提出基于连接强度的蚁群聚类方法JSACO，该算法把连接强度融入到拾起、放下的规则中，并在聚类的过程中利用放下规则舍弃一些不良数据，最后得到聚类结果。文献[12]提出一种多智能体进化机制的模块检测算法，该算法通过智能体间的竞争、交叉和变异3种主要操作完成种群的进化。文献[13]针对蛋白质网络噪声高、得到的模块精度不高等问题，融合蛋白质的基因本体信息，提出一种改进的蚁群寻优机制的模块检测算法NACO-FMD。文献[14]根据细菌觅食的4种生物机制，提出一种基于细菌生物机制的模块检测算法BBM-FMD。它们取得的优良结果表明群智能的方法已成为目前解决PPIN功能模块检测问题最具有竞争力的方法之一。但是，收敛速度慢、易陷入局部最优是制约其在PPIN功能模块检测应用中的主要瓶颈。因此，研究高效的群智能求解算法是必要的。

花授粉算法是一种新型、高效的群智能算法，一方面利用最优花粉参与解的进化，加快了解的收敛速度；另一方面，采用Levy飞行机制进行全局搜索有利于跳出局部最优解。鉴于此，本研究提出一种基于花授粉算法的蛋白质相互作用网络功能模块检测方法。FPA-FMD采用随机游走的方式完成花粉个体的初始化，种群中的每个花粉根据切换概率选择进化方式，在自花授粉过程中，花粉随机的选择重组、取优策略得到下一代花粉。在异花授粉过程中，该算法把最优花粉作为进化过程中的信息交互，并根据Levy和差异度两种步长向量引导种群的进化。最后为了增加种群的多样性，采用随机移民策略更新种群中的较差个体。仿真试验表明，新算法在各项指标上均具有很强的竞争力。

1 花授粉算法

花授粉算法是2012年英国剑桥大学学者杨新社受自然界中花朵授粉现象启发而提出的一种启发式算法^[15]。该算法具有结构简单、鲁棒性强、执行效率高和稳定性强等优点，在很多应用领域已经表现出了非常好的特性^[16-17]。在介绍花授粉算法之前，先介绍一下植物授粉的相关机理。

1.1 植物授粉机理

每一朵花含有少则几个、多则成千上万的花粉配子。花朵授粉是花粉配子向雌蕊的柱头简单的转移过程^[18]。自然界中花朵授粉的方式大致分为两种：自花授粉和异花授粉。其中，自花授粉是同一朵花自身传粉或同一植株的不同花间传粉，主要通过风和扩散完成传粉。而异花授粉是不同植株的花间传粉，主要依靠昆虫和鸟类等传粉者完成传粉，该过程中有些传粉者习惯性地为某些特定种类的花朵传粉而绕过其它种类的花朵，这种现象叫做花的恒常性。生物学家达尔文认为植物的授粉方式对子代有重大的影响^[19]：自花授粉产生的子代生活力弱，适应环境的能力差，仅可以保证子代的产量；而异花授粉产生的子代是来自不同植株的优良基因的结合，故其生存能力更强，进而能够保证子代的质量。

1.2 花授粉算法

花授粉算法是一种基于植物授粉机理的群智能优化算法。为了使该算法简单易行，根据花朵授粉的特点，假定算法满足如下理想化规则：

(1) 异花授粉时，传粉者通过Levy飞行进行花粉的传播，该过程映射为全局搜索过程。

(2) 自花授粉映射为局部搜索过程。

(3) 花的恒常性与授粉过程中花的相似性有关。

(4) 授粉方式的改变通过切换概率$p$($p$∈[0, 1])来控制。即当随机数$r$＜$p$时，执行自花授粉，否则执行异花授粉。

花授粉算法中每个花粉对应求解问题的一个可行解。在该算法的初始阶段随机生成一个规模为$M$的种群，种群中的第$i$个花粉用向量$\boldsymbol{X}_{i}$=($x$$_{i,1}$, $x$$_{i,2}$, …, $x$$_{i,k}$, …, $x$$_{i,D}$)表示，其中$x$$_{i,k}$表示第$i$个花粉的第$k$维的数值，$D$是求解问题的维数。接下来的优化过程主要包括自花授粉和异花授粉两种形式，授粉方式的选择依据切换概率$p$。

自花授粉的更新公式为

$ \mathit{\boldsymbol{X}}_i^{t + 1} = \mathit{\boldsymbol{X}}_i^t + \varepsilon \cdot \left( {\mathit{\boldsymbol{X}}_j^t - \mathit{\boldsymbol{X}}_k^t} \right), $

(1)

式中：$\boldsymbol{X}^{t}_{i}$、$\boldsymbol{X}^{t+1}_{i}$分别为第$t$代、第$t$+1代的花粉个体；$\boldsymbol{X}^{t}_{j}$、$\boldsymbol{X}^{t}_{k}$是种群中异于花粉$\boldsymbol{X}^{t}_{i}$的两个随机个体；$ε$为[0, 1]之间的随机数(除特殊指定外，本研究提到的随机数一律服从均匀分布)。

异花授粉过程中，传粉者遵从Levy飞行规律，飞行相对较远的路程进行授粉，其更新公式为

$ \mathit{\boldsymbol{X}}_i^{t + 1} = \mathit{\boldsymbol{X}}_i^t + \mathit{\boldsymbol{L}} \cdot \left( {\mathit{\boldsymbol{X}}_i^t - {\mathit{\boldsymbol{g}}_ * }} \right), $

(2)

式中：$\boldsymbol{L}$是一个$D$维步长向量，向量的每一维均是一个服从Levy分布^[20]的随机数；$\boldsymbol{g}_{*}$是种群中的最优花粉。在该优化过程中，最优花粉$\boldsymbol{g}_{*}$为子代提供优良的“基因”，恰好印证了达尔文学说中异花授粉的子代质量好的见解。花授粉算法的大致流程见算法1。

算法1 FPA

$\mathbf{Step}$ 1 初始化：

               初始化种群规模$M$、最大进化代数$T$和切换概率$p$等参数；

               随机产生初始种群；

$\mathbf{Step}$ 2 寻找初始种群的最优花粉；

$\mathbf{Step}$ 3 While $t$＜$T$

                 for $i$=1 to $M$

                   if (随机数$r$＜$p$) then依据公式(1)执行自花授粉；

                   else依据公式(2)执行异花授粉；

                   endif

                 endfor

                 $t$=$t$ + 1;

                 更新当前种群的最优花粉；

                 endwhile

$\mathbf{Step}$ 4 输出最优花粉。

2 FPA-FMD

FPA-FMD算法利用花授粉算法的寻优机制完成PPIN功能模块检测。该算法的大致思路是首先初始化种群，然后依据花授粉的机制对种群进行优化，最后得到满足要求的PPIN功能模块划分结果。

2.1 花粉的初始化

FPA-FMD中每个花粉代表PPIN功能模块检测问题的一个解。每个花粉用一个一维数组表示，如$X$={$a$$_{1}$, $a$$_{2}$, …, $a$$_{i}$, …, $a$$_{N}$}，其中，$i$为蛋白质节点的编号，$N$为PPIN中蛋白质节点的数量，$a$$_{i}$表示PPIN中一条从节点$i$到节点$a$$_{i}$的边。本研究采用随机游走的方式对花粉初始化，该过程包括如下五个步骤：

第一，随机地对网络中所有蛋白质节点从1到$N$进行编号，图 1为一个PPIN的示例。通过图 1可以得到由每个节点的直接邻居节点组成的邻接链表，如图 2所示。

第二，分别计算邻接链表中每个节点与邻居节点的相似性度量，相似性度量可定义为

$ {C_{ij}} = \frac{{m{S_{ij}} + n{f_{ij}}}}{{m + n}}, $

(3)

式中：$S$$_{ij}$、$f$$_{ij}$分别表示节点$i$、$j$的结构相似性和功能相似性；$m$、$n$为常数，分别代表结构特征和功能特征在相似性度量中所占的比例的计算式为

$ {S_{ij}} = \frac{{\left| {\mathit{\Gamma }\left( i \right) \cap \mathit{\Gamma }\left( j \right)} \right|}}{{\sqrt {\left| {\mathit{\Gamma }\left( i \right)} \right|\left| {\mathit{\Gamma }\left( j \right)} \right|} }}, $

(4)

$ {f_{ij}} = \frac{{\left| {{g^i} \cap {g^j}} \right|}}{{\left| {{g^i} \cup {g^j}} \right|}}, $

(5)

式中：$\mathit{Γ}$($i$)、$\mathit{Γ}$($j$)分别为节点$i$、$j$的邻接节点集合；|$\mathit{Γ}$($i$)|、|$\mathit{Γ}$($j$)|分别为集合$\mathit{Γ}$($i$)、$\mathit{Γ}$($j$)中元素的个数; $g$$^{i}$、$g$$^{j}$分别为节点$i$、$j$对应GO注释信息的集合。

第三，令节点$i$为起始节点，从$i$的邻接链表中找出相似性度量大于$e$($e$为相似性阈值)的节点。假若$j$满足条件, 对应到花粉的编码中，把一维数组下标为$i$的位置赋值为$j$。

第四，把$j$作为起始节点，循环执行第三步直至完成花粉对应的一维数组的编码。其执行结果如图 3所示。

第五，根据图 3中节点相邻接的关系，连通的节点在同一个模块，不连通的节点在不同的模块，可解码为如图 4所示的结果。图 4即为初始网络图 1的一个功能模块划分。

得到PPIN功能模块划分的一个解后，便可衡量该解的好坏。在FPA-FMD算法中，为了突显模块内连接密集、模块间连接稀疏的特性，采用模块密度函数作为评价花粉适应度的标准。花粉的适应度越大，其对应的解也越好。花粉适应度为

$ {\rm{Adaptation}}\left( {{X_i}} \right) = \sum\limits_{h = 1}^C {\left[ {\frac{{{e_h}}}{{\left| E \right|}} - {{\left( {\frac{{{d_h}}}{{2\left| E \right|}}} \right)}^2}} \right]} , $

(6)

式中：$C$为花粉$X$$_{i}$解码后对应的功能模块数；$e$$^{h}$为第$h$个功能模块中节点间的连接数；$d$$_{h}$为第$h$个功能模块中所有节点的度之和；|$E$|为整个网络中的连接数。

2.2 基于花授粉机制的优化过程

为了模拟自然界中花朵的分布结构，用图 5所示的二维循环网格作为种群的进化环境，其中每一朵花代表一个花粉。FPA-FMD的优化过程主要包括自花授粉、异花授粉和随机移民三种进化机制。其中授粉方式的选择依据切换概率$p$。

2.2.1 自花授粉

自花授粉对应局部搜索过程。结合自花授粉是近距离授粉的生物学特点，假若对图 5中第二行、第二列的红色花粉$X$$_{i}$进行自花授粉，从其8个邻居花粉(红色花粉的邻居花粉为其上、下、左、右、左上、左下、右上、右下的蓝色花粉)中随机选择两个花粉$X$$_{j}$、$X$$_{k}$，三个花粉随机地选择重组策略或取优策略进行优化。

重组策略：随机产生一个由数字0、1、2组成的向量，该向量的长度等于$N$，其中$N$是网络中蛋白质的个数，也是花粉的编码长度。向量中所有为0的位置，子代花粉$X^′_{i}$的对应位取自花粉$X_{i}$；对应1的位置，$X^′_{i}$取自$X_{j}$；对应2的位置，$X^′_{i}$取自$X_{k}$。其执行结果如图 6所示。

重组策略是花粉$X$$_{i}$与两个邻居花粉$X$$_{j}$、$X$$_{k}$简单的“基因重组”过程，其子代$X^′_{i}$的适应度可能不高，这恰好印证了达尔文学说中自花授粉子代质量差的见解。

取优策略：随机产生一个由0、1组成的掩码向量，向量的长度等于$N$。向量中所有为0的位置，子代花粉$X^′_{i}$的对应位直接取自花粉$X$$_{i}$；对应1的位置，$X^′_{i}$取自$X$$_{i}$、$X$$_{j}$、$X$$_{k}$对应位相似度较大的，执行结果如图 7所示。例如，向量$\boldsymbol{b}$的第4位的值为“1”，三个父代花粉$X$$_{i}$、$X$$_{j}$、$X$$_{k}$的第4位分别为“3”“6”“2”，则从相似度$C$$_{43}$、$C$$_{46}$、$C$$_{42}$中选择最大的，假若$C$$_{42}$为最大的相似度，则$X^′_{i}$的第4位取自$X$$_{k}$，最终$X^′_{i}$的第4位编码为“2”。

2.2.2 异花授粉

异花授粉对应全局搜索过程。假若对花粉$X$$_{i}$进行异花授粉，从当前种群中选出最优花粉$g$$_{*}$，花粉$X$$_{i}$、$g$$_{*}$随机地选择基于Levy机制的变异策略或基于差异度的自适应变异策略进行优化。

基于Levy机制的变异策略：按照Levy飞行机制映射生成一个由0、1组成的Levy向量$\mathbf{α}$，$\mathbf{α}$的长度等于$N$。$\mathbf{α}$中对应0的位置，子代花粉的对应位直接取自$X$$_{i}$；对应1的位置，子代花粉取自$X$$_{i}$、$g$$_{*}$对应位相似度较大的。

结合Levy分布的特点，映射Levy向量$\mathbf{α}$的过程如下。

(1) 为整个种群生成一个服从Levy分布的随机数集$L$并按降序排列，$L$的大小等于$N$-1；

(2) 每次执行Levy策略时，重新生成一个服从Levy分布的随机数$r$，并把$r$按序插入到$L$中得到集合$L$′，假若$r$在$L$′中的排序是$m$；

(3) 生成一个含有$m$个1的向量$\mathbf{α}$，$\mathbf{α}$的长度为$N$，$m$个1均匀地分布在$\mathbf{α}$中，其余位用0补齐，该向量$\mathbf{α}$称为Levy向量。

执行基于Levy机制的变异策略时，Levy向量$\mathbf{α}$中1的个数大部分情况下在$N$/2上下浮动，但偶尔会有突跳现象，即出现1的个数较多或较少的现象。Levy向量$\mathbf{α}$中1的个数扮演着步长的角色，大部分情况下步长稳定，偶尔会有跳跃，故在种群的进化过程中，该策略具有跳出局部最优的特性。

基于差异度的自适应变异策略：根据式(7)计算$X$$_{i}$、$g$$_{*}$的差异度，假若等于$k$。产生一个由0、1组成的差异度向量$\boldsymbol{c}$，$\boldsymbol{c}$的长度为$N$，其中1的个数为$k$，且均匀分布在$\boldsymbol{c}$中，其余位用0补齐，该过程如图 8所示。$\boldsymbol{c}$中对应0的位置，子代花粉直接取自$X$$_{i}$；对应1的位置，子代花粉取自$X$$_{i}$、$g$$_{*}$对应位相似度较大的。

两个花粉的差异度定义为

$ {\rm{Difference}}\left( {{X_i},{g_ * }} \right) = \sum\limits_{j = 1}^N {\left\{ \begin{array}{l} 0\;\;\;{\rm{if}}\;{X_{i,j}} = {g_{ * ,j}}\\ 1\;\;\;{\rm{if}}\;{X_{i,j}} \ne {g_{ * ,j}} \end{array} \right.} , $

(7)

其中，$X$$_{i,j}$、$g$$_{*,j}$分别为花粉$X$$_{i}$、$g$$_{*}$的第$j$维的编码。花粉$X$$_{i}$、$g$$_{*}$的差异度越大，表明花粉$X$$_{i}$与最优花粉$g$$_{*}$的差距越大，从而$X$$_{i}$的进化空间也越大。由基于差异度的自适应变异策略可知，差异度向量为1的位越多，子代$X^′_{i}$向最优花粉进化的自适应步伐也越大。

2.2.3 随机移民策略

一旦种群初始化完成，其子代的编码均取自某个父代，显然种群中没有新鲜血液流入。尤其是种群进化后期，种群的多样性严重丧失，使得FPA-FMD算法易陷入局部最优。鉴于此，当种群完成一代进化后，采用随机移民策略以增加种群的多样性。

随机移民策略的具体步骤为：(1)对种群中的个体按适应度由大到小的顺序进行排列，移除(0.05$M$+$q$)个较差个体，其中，$M$是种群的大小，$q$是最优花粉适应度保持不变的迭代次数。(2)移除后空缺的位置重新初始化新个体进行填充。

在该策略的执行过程中，最优花粉适应度保持不变的迭代次数越大，说明种群多样性丧失越严重，相应的本研究设计移除个体的数量也随之增加。

2.3 算法描述与分析

FPA-FMD算法的核心思想是结合自花授粉和异花授粉机制对种群进行进化，最后采用随机移民策略对种群进行更新。FPA-FMD算法的运行流程见算法2。

算法 2 FPA-FMD

Input：PPIN对应的图$G$($V$, $E$)，|$V$ |=$N$，GO信息；

Output：PPIN功能模块集合$C$；

$\mathbf{Step}$ 1 初始化：

                  初始化参数：$M$(种群中花粉的个数)、$e$(相似度阈值)、$p$(自花授粉和异花授粉的切换概率)、$Q$(最优花粉适应度不变的最大迭代次数)、$λ$(合并阈值)、$δ$(过滤阈值)；

依次计算任意两个蛋白质节点对之间的相似性；

$\mathbf{Step}$ 2 产生初始种群：

            for $s$=1 to $M$

                  $i$=1~$N$之间的随机整数

                  首先把第$i$个蛋白质节点作为起始节点，然后从$i$的邻居节点中选择满足条件的节点$j$，接下来以节点$j$为起点，如此往复。

                  endfor

$\mathbf{Step}$ 3 花授粉优化种群：

            计算种群中每个花粉的适应度；

            $\text{max}^{0}$=最优花粉适应度；

            最优花粉适应度不变的代数$q$=0；

            while $q$＜$Q$

                 for $s$=1 to $M$

                   if(随机数$r$$_{1}$＜$p$)then自花授粉

                     if(随机数$r$$_{2}$＞0.5)then执行重组策略；

                     else执行取优策略；

                     endif

                 else异花授粉

                     If(随机数$r$$_{3}$＞0.5)then执行基于Levy机制的变异策略；

                     else执行基于差异度的自适应变异策略；

                 endif

               endif

             endfor

            执行随机移民策略；

            If ($\text{max}^{t}$==$\text{max}^{t-1}$) then $q$=$q$+1；

            else $q$ = 0；

            endif

            endwhile

$\mathbf{Step}$ 4 后处理过程：执行合并、过滤操作^[12]；

$\mathbf{Step}$ 5 输出$\text{max}^{\text{T}}$对应的功能模块检测结果, $C$，$T$为最大迭代次数。

基于算法2中的描述，对FPA-FMD算法进行时间复杂度分析：设PPIN中节点最大的度为$d_{1}$，最大功能模块包含$d_{2}$个节点，种群初始化的时间复杂度为$O$($d_{1}$·$N$·$M$)，花授粉优化种群的时间复杂度为$O$($T$·($d_{2}$+$M$)·$N$)，后处理阶段和输出部分的时间复杂度为$O$($C^{2}$+$C$)≈$O$($C^{2}$)。由此FPA-FMD的整体时间复杂度为$O$($d$$_{1}$·$N$·$M$+$T$·($d$$_{2}$+$M$)·$N$+$C$$^{2}$)。由于PPIN是具有无标度性和小世界性的网络，因此$d$$_{1}$≪$N$，$d$$_{2}$＜$N$，$C$≪$N$。最终FPA-FMD的时间复杂度可近似为$O$($T$·($d$$_{2}$+$M$)·$N$)。

3 仿真试验与结果分析 3.1 试验环境及数据

本试验的运行环境：Windows7操作系统，i5-3470 CPU、4.00 G内存，运行工具是eclipse。

本研究使用3个常用的公共数据集：MIPS数据集、DIP核心数据集和Gavin数据集。其中MIPS数据集包含4545个节点和12318条边；DIP核心数据集包含2508个节点和5626条边；Gavin数据集包含1430个节点和6531条边。算法中用到的GO信息可以通过网站bioDBnet(http://biodbnet.abcc.bcc.Ncifcrf.gov/db/db2db.php)查询。除此之外，为了检测本算法的有效性，利用文献[21]提供的428个标准模块作对比。

3.2 评价指标

本研究使用两组常用的度量标准来评价试验结果的质量^[22]。

3.2.1 精度、召回率和F度量

精度(Precision)、召回率(Recall)以及F度量(F-measure)是PPIN功能模块检测问题中常用的度量指标，在计算这些指标时用到邻域亲和评分(NA)标准，NA是一种评价预测模块与标准模块一致性的度量，其定义为

$ {\rm{NA}}\left( {p,b} \right) = \frac{{{{\left| {{V_p} \cap {V_b}} \right|}^2}}}{{\left| {{V_p}} \right| \times \left| {{V_b}} \right|}}, $

(8)

式中：预测模块表示为$p$=($V$$_{p}$, $E$$_{p}$)；标准模块表示为$b$=($V$$_{b}$, $E$$_{b}$)；$V$表示节点；$E$表示边。若NA($p$, $b$)≥$w$(一般取$w$=0.2)，可认为预测模块$p$和标准模块$b$匹配。另外，预测的功能模块集合用$P$表示，标准功能模块集合用$B$表示，则$P$中至少与一个标准模块相匹配的模块数可表示为$N$$_{cp}$=|{$p$|$p$∈$P$, ∃$b$∈$B$, NA($p$, $b$)≥$w$}|，换个角度，$B$中至少和一个预测模块相匹配的模块数表示为$N$$_{cb}$=|{$b$|$b$∈$B$, ∃$p$∈$P$, NA($p$, $b$)≥$w$}|，于是，PPIN功能模块检测方法的精度和召回率指标可定义如下：

$ \text{Precision} = \frac{{{N_{cp}}}}{{\left| P \right|}}, $

(9)

$ {\rm{Recall}} = \frac{{{N_{cb}}}}{{\left| B \right|}}。$

(10)

F-measure是Precision和Recall的调和平均值，用于衡量总体性能，其表示方法为

$ {\rm{F - measure}} = \frac{{2 \times \text{Precision} \times {\rm{Recall}}}}{{\text{Precision} + {\rm{Recall}}}}。$

(11)

3.2.2 敏感度、正的预测率和准确度

敏感度(sensitivity，Sn)、正的预测率(positive predictive value，PPV)和准确度(accuracy，Acc)是另一组评价模块检测方法性能的衡量指标。其定义为

$ \text{Sn} = \frac{{\sum\limits_{i = 1}^n {\mathop {\max }\limits_j \left\{ {{T_{ij}}} \right\}} }}{{\sum\limits_{i = 1}^n {{N_i}} }}, $

(12)

$ {\rm{PPV}} = \frac{{\sum\limits_{j = 1}^m {\mathop {\max }\limits_i \left\{ {{T_{ij}}} \right\}} .}}{{\sum\limits_{j = 1}^n {{T_{.j}}} }}, $

(13)

式中：$m$=|$V$$_{p}$|，$n$=|$V$$_{b}$|；$T$$_{ij}$为标准模块$b$$_{i}$与预测模块$p$$_{j}$所共有的蛋白质数量；$N$$_{i}$为标准模块$b$$_{i}$包含的蛋白质数量；$T$$_{.j}$=$∑\limits^{m}_{j=1}T_{ij}$。与F度量类似，准确度Acc也是一种综合度量，可用灵敏度和正的预测率的一种几何平均来表示

$ {\rm{Acc}} = \sqrt {{\rm{Sn}} \times {\rm{PPV}}} 。$

(14)

3.3 试验比较

力求得到较好的试验结果，对FPA-MFD算法中用到的参数进行了试验测评，用Precision、Rec-all、F-measure、Sn、PPV和Acc作为评价指标。其中每个参数均是在其它参数不变的情况下进行试验，同时6种指标为独立运行15次的平均值，最后综合考虑6个指标来确定参数的取值。通过试验比较，FPA-MFD算法的参数设置如下：种群的大小$M$=100，结构相似性和功能相似性在相似性度量中的比例$m$:$n$=1:4，相似度阈值$e$=0.2，自花授粉和异花授粉的切换概率$p$=0.8，最优花粉适应度保持不变的最大迭代次数$Q$=20，合并阈值$λ$=1.5，过滤阈值$δ$=0.08。用于对比的其他算法的参数和原论文保持一致。

本研究首先将FPA-FMD与MCODE、jerarca、coach、cfinder、MCL和NACO-FMD 6种经典算法在3个不同规模的数据集上进行了对比。试验结果如表 1所示。

针对每种算法，表 1分别列出了预测模块数、模块平均大小、至少与一个标准模块相匹配的预测模块数$N$$_{cp}$及至少与一个预测模块相匹配的标准模块数$N$$_{cb}$。以MIPS数据集为例介绍表格的含义，在MIPS数据集上，FPA-FMD算法检测到550个功能模块，其中有183个模块与257个标准模块相匹配，检测到的模块平均包含2.85个蛋白质。在表 1中，$N$$_{cp}$指标上，FPA-FMD算法在数据集MIPS、DIP和Gavin分别取得了第一、第二和第二的结果。指标$N$$_{cb}$在3个数据集上取得的结果与$N$$_{cp}$完全相同。这说明FPA-FMD算法有较多的检测模块与标准模块相匹配，从而反映了FPA-FMD算法性能优良。

为了进一步展现FPA-FMD算法的整体性能，图 9~11分别给出了7种算法在MIPS、DIP和Gavin 3个数据集上6个指标的对比结果。

从3幅图可以看出FPA-FMD算法对应折线的整体轮廓均在相对靠上的位置，这表明该算法的整体性能很好。接下来，进一步分析FPA-FMD在6个指标上的具体表现。首先，对于F-measure和Acc两项综合指标，FPA-FMD算法在3个数据集中均表现最佳，并大幅度地超过其他6种算法。对于F-measure指标，在3个数据集上FPA-FMD较排名第二的算法分别高出16.3%(NACO-FMD)、5.2%(NACO-FMD)和6.6% (NACO-FMD)。对于Acc指标，在3个数据集上FPA-FMD高出排名第二的算法分别为4.1%(jerarca)、0.8%(jerarca)和1.7%(MCL)。其次，FPA-FMD算法在PPV指标上表现也不错：在MIPS和DIP数据集上排名第一；在Gavin数据集上，以低于NACO-FMD算法0.4%的微弱差距获得第二名的成绩。再次，FPA-FMD算法在Recall指标上表现优良：在MIPS数据集上排名第一；在DIP和Gavin数据集上均低于MCL算法，排名第二。综合以上4个指标，FPA-FMD均取得了不错的结果的原因为：主要是因为本研究在每次迭代中突出了对较优解的偏爱，能够更好地引导解向最优解进化；另一方面，两种变异策略的使用分别从自适应步长和突跳步长的角度交相呼应地引导种群的进化，使算法获得更好的解。最后，在Precision和Sn两项指标上，FPA-FMD算法表现一般但仍有优势。对于Precision指标，FPA-FMD算法与另外6种算法相比，在3个数据集上排名分别为第二、第三和第三。其中，mcode在3个数据集上均排名第一，cfinder在DIP数据集上排名第二，NACO-FMD在Gavin数据集上排名第二。本研究在该指标上表现一般的原因为:由式(9)和表 1可知，mcode之所以在3个数据集上均取得最好结果是因为在利用式(9)求解该指标时，mcode方法对应的位于分母位置的预测模块数远远小于其他的算法；对于Sn指标，FPA-FMD算法与另外6种算法相比，在3个数据集上排名分别为第三、第三和第二。FPA-FMD在该指标上取得的结果一般原因是本研究解的初始化方法使其无法识别重叠的功能模块，致使预测的各个功能模块中均无重复的蛋白质，进而模块的平均大小偏小，最终导致计算Sn指标时结果不突出。综上所述，7种算法在3个数据集上的对比试验展现了FPA-FMD算法在蛋白质功能模块检测上具有优良的性能，是一个很有竞争力的算法。

4 结论

本研究基于花朵授粉原理提出了一种PPIN功能模块检测的新方法FPA-FMD，该方法是基于群集智能思想进行蛋白质模块检测的一个新探索。FPA-FMD最主要的特点是结合花朵授粉的生物机理提出了重组、取优、基于Levy机制的变异和基于差异度的自适应变异4种行之有效的优化策略。并且，采用随机移民策略，用新生成的个体替换种群中的较差个体以便跳出局部极值。最终在3个公共PPIN数据集上的试验表明，FPA-FMD算法相较其他6种经典算法，整体性能优良并且在F度量和准确度两项综合指标上具有绝对优势。

FPA-FMD算法的提出，一方面拓展了花授粉算法的应用领域；另一方面，对分析其他具有类似结构的复杂网络如Web网、因特网和人际关系网等具有一定的借鉴意义。