蛋白质是所有生命的物质基础,也是一切生命活动的体现者. 蛋白质在参与生命活动时,很少以独立个体的方式存在,而是以通过相互作用构成大分子复合物的形式完成对应的生物学功能. 在一个生命有机体内,所有蛋白质之间的相互作用组成的生物分子关系网络叫作蛋白质相互作用(protein-protein interaction,PPI)网络. 不同的时间和空间阶段通过相互作用共同参与某一特定分子进程的蛋白质集合称为功能模块. 对PPI网络进行研究与分析的一个主要目的是检测出其中的功能模块,而聚类是功能模块检测的常用方法之一. 从PPI网络数据中检测功能模块是后基因时代蛋白质组学研究的重要内容,它有助于理解蛋白质之间的相互作用以及各种生物学过程,能够揭示疾病的发生机制,为新药研发提供重要的理论基础 ^{[ 1]} .

近10年间,大规模PPI网络数据的获得,使得以数据挖掘、机器学习为基础的计算方法迅速兴起. 依据所采用的计算模型和机理,可以将其划分为基于传统图理论的方法和基于非传统图理论的方法两大类 ^{[ 2]} . 其中,基于传统图理论的检测方法依据PPI网络的拓扑结构信息完成聚类,主要有基于密度的检测方法、基于层次的检测方法、基于划分的检测方法等 ^{[ 3]} . 例如,文献[4]提出了基于密度的检测(molecular complex detection,MCODE)方法. 该方法首先选取局部邻域密度最大的节点作为初始的功能模块,然后向外扩张该节点形成最终的功能模块. MCODE能够有效地检测出密度大的功能模块,但在稀疏的PPI网络中效果不佳. 文献[5]提出了基于层次的检测方法JERARCA,该方法先计算PPI网络的距离矩阵,再将PPI网络的距离矩阵转换成为层次结构的树,然后根据模块内和模块间节点的连接分布进行最优层次划分得到功能模块. JERARCA方法在聚类过程中某个节点的层次分类错误,将导致其下层节点的分类不正确,因此该方法对噪声数据非常敏感. 基于非传统图理论的检测方法是将其他机理融合于图聚类过程,主要有基于流模拟的检测方法、基于核心-附属关系的检测方法、基于群智能的检测方法等. 例如,文献[6]提出了一种基于流模拟的马尔可夫聚类(Markov clustering,MCL)检测方法,该方法重复模拟流在PPI网络中的扩展和收缩行为,将PPI网络划分为许多稠密子图作为最终的检测结果. MCL能够适应网络的变化,在一定程度上克服噪声数据的影响,具有很强的鲁棒性. 依据对实验所确定的蛋白质复合物的生物信息学分析,文献[7]提出了基于核心-附属关系的检测方法COACH. 该方法先抽取核心蛋白质,然后将附属蛋白质逐个分配到核心蛋白质周围,构成一个功能模块. COACH算法具有较强的功能模块识别能力,且能够检测出重叠的功能模块. 除此之外,近年来涌现了许多将群智能思想融合于图聚类过程的检测方法,该类算法通过模拟社会型生物群体间的协作行为实现功能模块的检测,展现了良好的检测质量. 文献[8]提出了改进的基于蚁群优化的PPI网络功能模块检测(new ant colony optimization functional module detection,NACO-FMD)方法,该方法结合PPI网络拓扑信息和基因本体(gene ontology)信息,设计PPI网络下的启发函数来指导蚁群寻优,得到了较好的检测结果. 文献[9]提出了基于多智能体进化机制的PPI网络功能模块检测方法MAE-FMD,该算法首先对PPI网络进行多智能体的解编码处理;然后通过随机游走的方式为每个智能体构建初始功能模块;最后通过3种进化算子实现种群的进化,取得了较好的结果. 文献[10]将蚁群聚类思想应用到PPI网络功能模块检测问题上,提出了基于蚁群聚类的PPI网络功能模块检测(ant colony cluster for functional module detection,ACC-FMD)方法,该算法首先选取种子节点,然后采用蚂蚁的拾起放下模型对网络中的蛋白质节点进行聚类,同时利用每代蚂蚁中的最优聚类结果和蛋白质之间的功能相似性评分更新相似性函数,将信息在不同代之间传递. 为提高检测质量,得到初始聚类结果后,ACC-FMD利用合并与过滤2个后处理操作对聚类结果进行修正,得出最终的聚类结果. 该方法与近年来一些流行的功能模块检测方法相比,具有一定的优势. 然而,该方法需要进行重复的拾起放下和大量的功能模块合并操作,导致求解时间过长.

为了克服ACC-FMD求解时间长的缺陷,本文提出一种快速的基于蚁群聚类的PPI网络功能模块检测(fast ant colony cluster for functional module detection,FACC-FMD)方法. FACC-FMD方法抽取稠密且具有高度共表达特性的子图作为核心组蛋白质,由于子图间具有较低的相似性,初始的聚类结果不需要合并,省去了大量的后处理时间. 而且该算法根据关键蛋白质的结构特性和生物特性计算蛋白质的关键性,并依据关键性高低对拾起放下操作进行了更严格的约束,从而减少了拾起放下的次数,加速聚类的过程.

1 相关工作

1.1 ACC-FMD方法

生物学家研究发现蚁群会将蚁穴中分散的蚂蚁尸体堆积成相对集中的几个大堆. 通过对蚁群清扫蚁穴行为的观察,学者们提出了蚁群聚类方法. 若将这些分散的蚂蚁尸体视为待聚类的数据对象,那么堆积而成的大堆则看作最终的聚类结果 ^{[ 11]} . 文献[10]将蚁群聚类技术运用到PPI网络的功能模块检测问题上,提出了ACC-FMD方法. 该方法将PPI网络表示为一个无向图 G=( V, E),其中 V表示蛋白质节点集合, E表示相互作用的集合. ACC-FMD算法主要包括如下4个过程.

1) 选取种子节点:种子节点是指在网络中局部密度较高的节点. ACC-FMD根据节点的聚类系数选取种子节点,将聚类系数大于阈值 ω的节点挑选出来构成种子节点集合 S,其中每个种子节点标注一个功能模块 . 对于网络 G=( V, E)中的任意节点 i,其聚类系数定义为

φ _i= $\begin{array}{c}\frac{2n_i}{\left|\mathit{Neigh}\right(i\left)\right|\left|\mathit{Neigh}\right(i)-1|}\end{array}$ (1)

式中:Neigh( i)为节点 i的直接邻居集合; n _i 为集合Neigh( i)中的节点之间相互作用的个数 .

2) 聚类过程:得到种子节点集合后,蚂蚁开始遍历每个种子节点的邻域进行聚类,节点邻域定义为

N( i) =Neigh( i)∪InNeigh( i) (2)

式中InNeigh( i)表示种子节点 i的间接邻居集合 . 在遍历过程中通过拾起概率模型确定是否拾起某个节点 . 若拾起该节点,则利用放下概率模型将已拾起的节点聚到其他种子节点标注的功能模块中,然后,进行新一轮的拾起放下操作;若没有拾起,则直接将它归属到该种子节点标注的功能模块中 . 当蚂蚁遍历完所有的种子节点时,形成自身的聚类结果 . 拾起概率模型 P _p( j)和放下概率模型 P _d( j)分别定义为

P _p( j) = $\begin{array}{c}{\left[\frac{k_p}{k_p+s(i,j)}\right]}^2\end{array}$ (3)

P _d( j) = $\begin{array}{c}\left\{\begin{array}{cc}2s(i,j),& s(i,j)<k_d\\ 1,& \mathit{其他}\end{array}\right.\end{array}$ (4)

式中: s( i, j)为节点 i和 j的结构相似度; k _p和 k _d为2个参数 . 结构相似度 s( i, j)通过归一化共同邻居定义,一般描述为

s( i, j) = $\begin{array}{c}\frac{\left|\tau \right(i)\bigcap \tau (j\left)\right|}{\sqrt[]{\left|\tau \right(i\left)\right|\left|\tau \right(j\left)\right|}}\end{array}$ (5)

式中 τ( i)为由节点 i的直接邻居和节点 i自身构成的集合 .

3) 信息传递:ACC-FMD通过节点之间的相似度将上一代最优解的信息传递给下一代 . 该方法通过模块化密度来评价解的质量,其定义为

D= $\begin{array}{c}\stackrel{m}{\sum _{h=1}}\end{array}\begin{array}{c}\frac{2l_h-{\overline{l}}_h}{n_h}\end{array}$ (6)

式中: m为预测到的功能模块的数量; l _h 为模块 h中所包含的节点之间存在的边数; $\begin{array}{c}{\overline{l}}_h\end{array}$ 为一个端点在模块内,另一个端点在模块外的边的数量; n _h 是模块中节点的个数 . D值越大,表明解的质量越好 . 每代聚类结束后,选出 D值最大的聚类结果(即最优解)更新相似度,使得初始的聚类结果逐渐地稳定在全局最优解周围 . 其相似度更新方式为

s( i, j) =(1 +f _ij ) ^count s( i, j)(7)

式中: i和 j为属于同一功能模块的2个节点;count为节点 i和 j聚在同一个功能模块中的次数; f _ij 为 i和 j的功能相似性评分,通过蛋白质的功能注释信息计算,定义为

f _ij= $\begin{array}{c}\frac{|g_i\bigcap g_j|}{|g_i\bigcup g_j|}\end{array}$ (8)

4) 后处理过程:经过一定次数的迭代后,对初始聚类结果进行合并与过滤2个后处理操作 . 合并操作是指合并2个相似度大于阈值的模块 . 模块 M _x 和 M _y 的相似度定义为

S( M _x , M _y ) = $\begin{array}{c}\frac{\sum _{i\in M_x,j\in M_y}r(i,j)}{\mathit{min}\left\{\right|M_x\left|,\right|M_y\left|\}\right.}\end{array}$ (9)

r( i, j) = $\begin{array}{c}\left\{\begin{array}{cc}1& i=j\\ f_{\mathit{ij}}& i\ne j,(i,j)\in E\\ 0& \mathit{其他}\end{array}\right.\end{array}$ (10)

对合并后的聚类结果过滤掉密度小于阈值的模块,形成最终的聚类结果 . 模块密度定义为

Density _G = $\begin{array}{c}\frac{\left.2\right|E_G|}{\left|V_G\left|(\right|V_G\right|-1)}\end{array}$ (11)

ACC-FMD算法具有蚁群聚类思想的正反馈性、自组织性和健壮性等优点 . 然而,该算法时间性能比较差,主要归于如下2个原因:1)算法抽取种子节点,根据相似度将非种子节点聚在种子节点周围构成功能模块 . 如果2个种子节点之间相似度比较大,那么聚类所形成的2个功能模块也较为相似,在后处理过程中,需要将这2个模块合并,而合并操作需要大量的计算,影响算法的时间性能 . 2)一个蛋白质节点可能在多个种子节点的邻域内,这样在聚类过程中会出现大量重复的拾起放下操作,导致聚类时间变长 .

1.2 基因表达信息与蛋白质共表达特性

生物学研究结果表明蛋白质在生命活动中具有一系列的特性,挖掘并利用这些特性有望提升功能模块检测方法的时间性能和质量 . 生物学家在实验中观察到超过一半的酵母菌基因呈现周期性表达的现象 . 基因编码蛋白质表现出类似的模式,特别是与能量和代谢相关的基因往往表现出强大的周期性 ^{[ 12]} . 基因表达信息可以直观地描述这一现象 . 具体来说,基因表达信息是用来表示蛋白质生命活动过程中的一组数据,它记录了蛋白质在多个时刻下的基因表达值 . 基因表达值越高,说明这个蛋白质在该时刻活性越高,越具有强表达性 . 如果用函数Exp( x, t)表示蛋白质 x在某时刻 t的表达值,随着 t的变化,该函数值会表现出周期性 . 尽管每个蛋白质都具有自己的表达周期以及表达强弱,但不同的蛋白质之间具有共表达特性 . 共表达特性从基因层面上描述了蛋白质之间的关系 . 利用这一特性可以在PPI网络中抽取出一部分特殊的蛋白质,辅助完成聚类 .

本文使用皮尔逊相关系数(Pearson correlation coefficient,PCC)来度量2个蛋白质之间共表达的强弱程度 . 若蛋白质 x和 y的表达函数为Exp( x, t)和Exp( y, t),则皮尔逊相关系数的定义为

Pcc( x, y) = $\begin{array}{c}\frac{1}{k-1}\end{array}\begin{array}{c}\stackrel{k}{\sum _{t=1}}\end{array}$ { $\begin{array}{c}\frac{\mathit{Exp}(x,t)-\mathit{Exp}\left(x\right)}{\sigma \left(x\right)}\end{array}$ }·{ $\begin{array}{c}\frac{\mathit{Exp}(y,t)-\mathit{Exp}\left(y\right)}{\sigma \left(y\right)}\end{array}$ }(12)

式中: k为样本数,即在基因表达信息中的时刻数; $\begin{array}{c}\overline{\mathit{Exp}}\end{array}$ ( x, t)和 $\begin{array}{c}\overline{\mathit{Exp}}\end{array}$ ( y, t)分别为蛋白质 x和 y在所有时刻下的平均表达值; σ( x)和 σ( y)分别为蛋白质 x和 y在所有时刻表达值的标准方差 . Pcc( x, y)取值范围是[ -1,1] . Pcc( x, y)大于0表示蛋白质 x和 y出现正相关,即一个蛋白质表达值增大,另一个蛋白质表达值也会增大,反之亦然 . Pcc( x, y)等于0说明蛋白质 x和 y不存在相关性 . 总的来说,Pcc( x, y)的绝对值越大,相关性越强 . 图1、2分别给出了一对蛋白质呈现出正相关和负相关的示意图. 图1中,蛋白质ymr261c和蛋白质yml049c的皮尔逊相关系数是0.59,2个蛋白质的基因表达值变化相同,呈现出正相关. 图2中,蛋白质ymr261c和蛋白质yml046w的皮尔逊相关系数是-0.74,2个蛋白质基因表达值的变化相反,呈现出负相关.

本文通过蛋白质之间的共表达特性来抽取核心组蛋白质和关键蛋白质.

功能模块一般由核心组蛋白质和附属蛋白质组成,相比之下,核心组蛋白质更能代表所处的功能模块. 从网络拓扑角度来描述,核心组蛋白质通常为小而稠密的子图 ^{[ 13]} ,核心组蛋白质之间的相互作用非常紧密. 从生物角度来描述,核心组蛋白质具有较高的共表达特性,并且被附属蛋白质包围 ^{[ 13]} .

图  1  ymr271c和ym l049c表现出正相关

Figure  1.  ymr271c show positive correlation with yml049c

下载: 全尺寸图片 幻灯片

图  2  ymr261c和yml046w表现出负相关

Figure  2.  ymr261c show negative correlation with yml046w

下载: 全尺寸图片 幻灯片

关键蛋白质是细胞生命活动中所必需的蛋白质,Winzeler等 ^{[ 14]} 将关键蛋白质定义为:通过基因剔除式突变将其移除后会造成有关蛋白质复合物功能的丧失,并导致生物体无法生存的蛋白质. 文献[15]指出,一个蛋白质与邻近蛋白质的相互作用越多,这个蛋白质对细胞的生存越重要,且成为关键蛋白质的可能性就越高. 并且该文献也指出在这些蛋白质中,与邻居节点具有较高共表达程度的蛋白质更易成为关键蛋白质. 由于关键蛋白质在功能上的重要性,它更倾向于成为功能模块内的蛋白质.

2 FACC-FMD方法

2.1 算法思想

ACC-FMD算法的大部分时间消耗在拾起放下和合并操作上,如何有效限制拾起放下操作次数的同时,增大求得的功能模块间的差异性从而减少合并操作,就成为ACC-FMD提升效率的关键.

FACC-FMD算法结合基因表达信息,生成稠密且具有高度共表达特性的核心组蛋白质,再通过蚁群聚类机制将蛋白质归属到核心组蛋白质周围以形成功能模块. 核心组蛋白质是一个子图,由于子图之间的差异性比原蚁群聚类算法中种子节点之间的差异性大,故求得的功能模块可能不再需要进行合并操作,从而有望提高算法的时间性能. 另外,相比于非关键蛋白质,关键蛋白质对功能模块的重要性更高. 以此为依据,FACC-FMD计算每个蛋白质的关键性,利用关键性对拾起放下进行严格的约束,从而减少拾起放下次数,提高聚类的效率.

2.2 基于基因表达信息的核心组蛋白质抽取

大量的合并操作会在一定程度上影响ACC-FMD算法的时间效率. 针对这一问题,FACC-FMD算法使用核心组蛋白质替代种子节点进行蚁群聚类. 依据前面的描述,核心组蛋白质应该具有以下2个特性:第一,核心组蛋白质是小而稠密的子图;第二,核心组蛋白质具有高度的共表达特性 . 依据这2个特性,新算法首先计算每个节点的聚类系数并且与设定的阈值进行比较,将大于阈值的节点抽取出来作为潜在的核心节点集Core . 然后,将Core中的节点扩展为核心组蛋白质 . 对于Core集合中每个节点 C _i ,将 C _i 和它的所有邻居放入一个集合 V _C,将它们之间的边放入到一个集合 E _C,构成子图 G _C =( V _C, E _C),再计算子图 G _C的密度和共表达值 . G _C的密度由式(11)计算得出 . G _C的共表达值用子图内节点之间的平均皮尔逊相关系数描述,定义为

coExp( G _C) = $\begin{array}{c}\frac{2}{n(n-1)}\end{array}\begin{array}{c}\sum _{i,j\in V_{G_C}}\end{array}$ Pcc( i, j)(3)

式中 n为核心内的节点数,共表达值的取值范围是[ -1,1],同样地,其值越大,表示 G _C的共表达程度越高 . 对于扩展得到的核心子图 G _C,它的密度值和共表达值可能会小于设定的阈值 λ和 δ,这时就要递归地删除 G _C中的节点,直到满足阈值的要求,形成最终的核心组蛋白质 . FACC-FMD删除关键性最低的节点,这是因为关键性高的蛋白质对生命活动更为重要,从而求得的核心组蛋白质更能体现功能模块的生物特性. 核心组蛋白质是一个稠密子图,因为子图之间的差异性较大,所以FACC-FMD可能不需要进行合并操作和过滤操作.

2.3 基于基因表达信息的蛋白质关键性计算

在ACC-FMD算法中,蛋白质节点在种子节点邻域内的次数就是其拾起放下次数. 为了克服该算法重复拾起放下次数过多的缺陷,FACC-FMD算法依据关键蛋白质的特征,计算每个蛋白质的关键性,利用关键性对拾起放下操作进行严格的约束,减少非关键蛋白质的拾起放下操作.

FACC-FMD使用边聚集系数(edge clustering coefficient,ECC) ^{[ 16]} 和皮尔逊相关系数来计算蛋白质关键性. 边聚集系数用于刻画网络中某个节点与其邻居节点的亲疏程度,给定PPI网络中的2个蛋白质节点 x和 y,用 N( x)、 N( y)分别表示节点 x和 y的直接邻居集合,则 x和 y的边聚集系数定义为

Ecc( x, y) = $\begin{array}{c}\frac{\left|N\right(x)\bigcap N(y\left)\right|}{\mathit{min}\left\{\right|N\left(x\right)|,|N\left(y\right)\left|\right\}}\end{array}$ (14)

Ecc( x, y)的取值范围是[0,1],其值越大,表明节点 x和 y联系越紧密 . 依据关键蛋白质与邻近蛋白质的相互作用较为紧密,且倾向于共表达的事实 ^{[17 - 18]} ,本文采用文献[19]的方法计算蛋白质节点 x的关键性度量 . 关键性度量的定义为

Pec( x) = $\begin{array}{c}\sum _{y\in N\left(x\right)}\end{array}$ Ecc( x, y)Pcc( x, y)(15)

Pec( x)不但考虑了节点 x和 y在网络中的亲疏程度,而且增加了节点 x和 y的共表达强度对关键性度量的影响,因此能有效地评价一个蛋白质的关键性 ^{[ 19]} . 鉴于基因表达数据与PPI网络数据的差别,Pec( x)取值在不同PPI网络上有所偏差 . 为了易于比较,对给定网络中计算得到的关键性度量进行归一化,将其取值范围转化到[0,1],所得值就是给定PPI网络中蛋白质的关键性,归一化方法为

Est( x) = $\begin{array}{c}\frac{\mathit{Pec}\left(x\right)-\mathit{min\; Pec}}{\mathit{max\; Pec}-\mathit{min\; Pec}}\end{array}$ (16)

式中max Pec和min Pec分别为整个网络中所有蛋白质关键性度量的最大值和最小值 . FACC-FMD在每次拾起放下之前会判断蛋白质的关键性是否大于阈值 θ,如果关键性小于 θ,不对它进行拾起放下操作,所以在蚁群聚类花费的时间肯定少于ACC-FMD .

FACC-FMD在蚁群聚类过程中,根据节点与核心组蛋白质的相似度计算拾起放下概率模型,再利用该模型完成聚类 . FACC-FMD的拾起概率模型和放下概率模型分别定义为

P _p( i) = $\begin{array}{c}{\left[\frac{k_p}{k_p+s(i,\mathit{Core})}\right]}^2\end{array}$ (17)

P _d( i) = $\begin{array}{c}\left\{\begin{array}{cc}2s(i,\mathit{Core}),& s(i,\mathit{Core})<k_d\\ 1,& \mathit{其他}\end{array}\right.\end{array}$ (18)

式中 s( i,Core)为蛋白质节点 i与核心组蛋白质的相似度 . 令 D _j 为核心组蛋白质 j的度, D _Core为核心组蛋白质的度之和,则 s( i,Core)由 i与每个核心组蛋白质的相似度进行加权求和得出,定义为

s( i,Core) = $\begin{array}{c}\sum _{j\in \mathit{Core}}\end{array}\begin{array}{c}\frac{D_{j}s(i,j)}{D_{\mathit{Core}}}\end{array}$ (19)

FACC-FMD在蚁群聚类过程中用式(17) ~(19)替换公式(3) ~(5) .

2.4 算法描述与分析

FACC-FMD利用基因表达信息刻画蛋白质之间的共表达特性,再结合蛋白质在PPI网络中的拓扑特性,抽取核心组蛋白质,利用与核心组蛋白质的相似度计算拾起放下概率模型,依据概率模型进行拾起放下操作. 由于核心组蛋白质之间的差异性较大,初始聚类结果不需要合并过滤操作. 在聚类过程中依据关键性对拾起放下操作进行严格的约束,减少了拾起放下次数. 综上所述,相比ACC-FMD,FACC-FMD不需要进行合并过滤操作,且具有较少的拾起放下操作次数,因此会拥有较高的检测效率. 新算法的框架如算法1所示.

算法1:FACC-FMD

输入:PPI网络数据、基因表达信息、基因本体信息.

输出:功能模块集合 M ₁, M ₂,…, M _k.

步骤1 初始化参数:蚂蚁数量 M、蚁群迭代数 T、拾起参数 k _p、放下参数 k _d、聚类系数阈值 ω、核心密度阈值 λ、核心共表达阈值 δ、关键性阈值 θ.

步骤2 计算节点 i的关键性Est:

for i = 1 to |V| do

compute Est( V _i );

end for

步骤3 构建功能模块核心集合Core:

Core =⌀;

for i = 1 to |V| do

if( φ _i ≥ ω) do

Core =Core∪ V _i ;

end if

end for

步骤4 扩展功能模块核心,修正不符合阈值的功能模块核心:

for i = 1 to |Core | do

Core _i= Core _i ∪Neigh(Core _i );

while

(Density(Core _i ) <λ && coExp(Core _i ) <δ)

do

Core _i= Core _i- min Est(Core _i );

end for

步骤5 蚁群聚类过程

for t =1 to T do

for m=1 to M do

for i=1 to |Core | do

for V _j ∈Neigh(Core _i ) do

if Est( V _i ) >θ do

利用拾起和放下规则对节点进行聚类;

end if

end for

蚂蚁 m得到自身的解;

end for

第 t代蚂蚁全部得到自身的解;

根据模块度评价标准,求出本次迭代的最优聚类结果,并利用聚类结果更新相似度;

end for

end for

从多次迭代中选取整个种群的最优解

步骤6 输出最优解 .

基于算法1的描述,对FACC-FMD算法做一个简单的分析:步骤1初始化参数的时间复杂度为常数级,即 O(1) . 步骤2计算PPI网络中每个节点的关键性 . 假设PPI网络中节点度的最大值为 d _max,计算任意一个节点的关键性的时间复杂度为 O( $\begin{array}{c}{d}_{\mathit{max}}^3\end{array}$ ),那么计算所有节点的关键性值的时间复杂度为 O( $\begin{array}{c}{d}_{\mathit{max}}^3\end{array}$ |V|) . 步骤3、4完成构建功能模块核心集合,其时间复杂度为 O( k ₁ d _max |V|)(0 <k ₁ <1),功能模块核心数量为 k ₁ |V|. 步骤5完成蚁群聚类,是算法的核心部分 . 假设一个节点经过拾起放下规则完成聚类的比较次数为 k ₂,而且 k ₂≤ k ₁ |V|,符合关键性阈值的节点个数为 k ₃ |V|(0 <k ₃ <1),那么步骤5的复杂度为 O( TMk ₃ |V|k ₂),可以化简为 O( TMk ₃ k ₁ |V| ²) . 综上,FACC-FMD算法的总的时间复杂度为上面所有步骤时间复杂度之和,即 O( TMk ₃ k ₁ |V| ²),由于 k ₁、 k ₂、 k ₃均与算法参数有关,可以与 T和 M一起看作常数,因此对于PPI网络中的功能模块检测来说,FACC-FMD是一种高效的算法 .

3 实验测试与分析

3.1 实验数据

本文使用通用的MIPS数据集 ^{[ 20]} 和DIP数据集 ^{[ 21]} 验证算法效果. 表1列出了数据集的详细信息. 实验中所需要的基因表达信息版本为GSE3431,包含7079个蛋白质的36个下的基因表达值,可通过网址http:∥www.ncbi.nlm.nih.gov/geo/query/acc.cgi?acc=GSE3431查询到. 为了评估检测结果的质量,使用文献[22]提供的标准数据集,该数据集包含428个功能模块. 实验环境是一台Windows 7 64位PC机,处理器型号是Intel i5-3470,3.2GHz CPU,4GB内存.

表  1  实验中所用到的数据集

Table  1.  Experimental data sets

数据集	版本	网址	节点数	边数
DIPCore	Scere20150429core	http:∥dip.doe-mbi.ucla.edu/	2452	5362
DIPFull	Scere20150429full	http:∥dip.doe-mbi.ucla.edu/	5103	22817
MIPS	PPI18052006	ftp:∥ftpmips.gsf.de/yeast/PPI/	4545	12318

下载: 导出CSV 

| 显示表格

3.2 评价标准

本文选用2种流行的评价功能模块检测方法性能的度量标准 ^{[ 21]} .

3.2.1 精度、召回率、F度量

为了度量所预测的功能模块与标准功能模块之间的匹配度,大多数学者使用邻域亲和(NA)评分来进行计算:

NA( p, b) = $\begin{array}{c}\frac{|V_p\bigcap V_b{|}^2}{\left|V_p\left|\times \right|V_b\right|}\end{array}$ (20)

式中: p=( V _p , V _p )表示预测的功能模块; b=( V _b , V _b )表示标准的功能模块 . 若NA( p, b) >ω,则认为预测模块 p与标准模块 b相匹配(一般取 ω=0 .2或0 .25) . 本文实验中 ω=0 .2 .

精度(precision)、召回率(recall) 和F度量(F-measure)是PPI网络功能模块检测中常用的一组评价指标 . 令 P为算法预测的功能模块集合, B为标准功能模块集合,则 P中至少与一个标准功能模块相匹配的模块数量可表示为 N _cp =|{ p|p∈ P,∃ b∈ B,NA( p, b)≥ ω} |;相对地, B中至少与一个预测的模块相匹配的模块数量为 N _cb =|{ b|b∈ B,∃ p∈ P,NA( p, b)≥ ω} |. 于是,功能模块检测方法的精度和召回率的定义为

Precision = $\begin{array}{c}\frac{N_{\mathit{cp}}}{\left|P\right|}\end{array}$ (21)

Recall = $\begin{array}{c}\frac{N_{\mathit{cb}}}{\left|B\right|}\end{array}$ (22)

F-measure是精度和召回率的综合指标,用于衡量整体性能,其大小为精度和召回率的调和平均值,即

F-measure= $\begin{array}{c}\frac{2\times \mathit{precision}\times \mathit{recall}}{\mathit{precision}+\mathit{recall}}\end{array}$ (23)

3 .2 .2 灵敏度、正的预测率、准确度

灵敏度(sensitivity,Sn)、正的预测率(positive predictive value,PPV)和准确度(accuracy,Acc)是最近提出的另一组评价模块检测方法性能的度量指标 . 设 m=|V _p| , n=|V _b| , T _ij 为标准模块 p _i 和预测模块 b _j 共有的蛋白质数量,灵敏度和正的预测率定义为

Sn = $\begin{array}{c}\frac{\stackrel{n}{\sum _{i=1}}\underset{j}{\mathit{max}}\left\{T_{\mathit{ij}}\right\}}{\stackrel{n}{\sum _{i=1}}{N}_i}\end{array}$ (24)

PPV = $\begin{array}{c}\frac{\stackrel{m}{\sum _{j=1}}\underset{i}{\mathit{max}}\left\{T_{\mathit{ij}}\right\}}{\stackrel{m}{\sum _{j=1}}{T}_j}\end{array}$ (25)

式中: N _i 为标准模块 i中所包含的蛋白质数量; T _j= $\begin{array}{c}\stackrel{n}{\sum _{i=1}}\end{array}$ T _ij. 一般来说,灵敏度越高说明算法对标准功能模块中的蛋白质具有越好的覆盖率;而正的预测率越高说明预测到的功能模块更有可能是标准的功能模块 . 准确度是一种综合评价,由灵敏度和正的预测率的几何平均值表示,即

Acc = $\begin{array}{c}\sqrt[]{\mathit{Sn}\times \mathit{PPV}}\end{array}$ (26)

这6种评价指标都是以数值形式来度量检测质量,它们的取值范围都是[0,1],值越大,表示该项指标越好.

3.3 实验比较

为了取得更好的实验结果,对FACC-FMD算法中涉及的参数做了实验,每种参数在其他参数不变的情况下独立运行10次,以精度、召回率、F度量、灵敏度、正的预测率和准确度作为评估的指标,取10次运行的平均结果. 通过综合比较6种评估指标来选取参数. 经过实验比较,FACC-FMD算法参数设置如下:蚂蚁个数 M=50,最大种群迭代数 T=20,聚类系数阈值 ω=0.65(DIPFull和MIPS中 ω=0.35),拾起参数 k _p =0.9,放下参数 k _d =0.2,核心组蛋白质密度阈值 λ=0.7,核心组蛋白质共表达阈值 δ=0.15,蛋白质的关键性阈值 θ=0.3. 用于比较的其他算法参数尽量保持与原论文中一致.

3.3.1 与原始ACC-FMD算法比较

为了验证本文提出的2个策略的有效性,在DIPCore、DIPFull和MIPS三个数据集上分别做了不同的实验. 分别在ACC-FMD基础上单独使用核心策略、单独使用关键性策略和同时使用这2个策略(即FACC-FMD)进行了对比,并且每个实验均使用了相同的参数.

表2展示了2种策略对时间性能的影响. 从 表2可以看出,使用核心策略后,在3个数据集上的聚类时间分别增长到了1.7倍、1.4倍和1.8倍,这是因为聚类时需要计算蛋白质节点与整个核心组蛋白质的相似度,增大了蚂蚁拾起、放下模型的计算量;但是由于在进行后处理操作时,并未进行合并过滤操作,仅仅是计算了所有模块间的相似度,因此总的运行时间大幅降低,分别缩短了75.4%、94.4%和48.6%. 类似地,使用关键性策略后,在3个数据集上的聚类时间分别缩短了58.1%、68.0%和38.8%,这是因为关键性策略减少了拾起、放下的次数;总运行时间分别缩短了83.5%、96.1%和63.6%. 不难发现,同时使用核心策略和关键性策略即FACC-FMD,可以使得在3个数据集上的总运行时间分别缩短了86.4%、95.6%和76.9%. 因此,FACC-FMD的2个策略能够显著改善算法的时间性能.

表  2  2种策略对运行时间的影响

Table  2.  Effects of two strategies on running time

数据集	算法	聚类时间/s	合并过滤时间/s	总运行时间/s
	ACC-FMD	26.075	170.539	196.614
DIPCore	核心策略	45.334	3.025	48.359
	关键性策略	10.932	21.533	32.465
	FACC-FMD	26.719		26.719
	ACC-FMD	469.699	17156.081	17625.780
DIPFull	核心策略	671.132	311.265	982.397
	关键性策略	150.447	530.517	680.964
	FACC-FMD	769.418		769.418
	ACC-FMD	132.015	389.765	521.780
MIPS	核心策略	236.556	31.594	268.150
	关键性策略	80.850	109.572	190.422
	FACC-FMD	120.513		120.513

下载: 导出CSV 

| 显示表格

图3~5展示了2种策略对检测质量的影响,可以看到,单独使用核心策略能够使召回率和F度量得到提升,这是因为根据节点与整个核心组蛋白质的相似度进行聚类能够模拟蚁群聚类思想中一个数据与某块数据的相似度,使得算法具有更高的准确性. 单独使用关键性策略在精度、召回率和F度量上与ACC-FMD算法相比会有小幅下降,但由于关键性高的蛋白质拾起放下次数并未大幅减少,而关键性高的蛋白质对功能模块更重要,预测到的功能模块更接近标准模块,检测结果的正的预测率指标反而有所提升. 从这3张图能够看出,当2种策略结合时即FACC-FMD方法,除了灵敏度之外,检测质量整体要优于ACC-FMD. 灵敏度之所以有小幅下降,是因为FACC-FMD在聚类时,根据关键性对拾起放下做了更严格的约束,关键性过低的蛋白质节点在聚类中不参与拾起放下,而这些蛋白质也可能是标准功能模块内的蛋白质,导致对标准功能模块内的蛋白质覆盖率降低. 根据以上的分析,可以得知,与ACC-FMD相比,FACC-FMD得到了更具有竞争性的结果.

3.3.2 与其他经典算法比较

为了进一步展现FACC-FMD的整体性能,下面将该算法与MCODE、JERARCA、MCL和COACH四种经典的PPI网络功能模块检测方法进行了实验比较,5种算法在3个不同数据集上的实验结果如 表3~5所示.

对于每种算法, 表3~5列出了功能模块检测结果的模块数、模块平均大小、覆盖率、至少与一个实际模块相匹配的预测模块数( N _cp)和至少与一个预测模块相匹配的实际模块数( N _cb). 以DIPCore数据集为例,FACC-FMD算法检测到500个功能模块,其中有311个功能模块和216个标准模块相匹配. 检测到的每个功能模块大约含有9.06个蛋白质节点. 综合上面3个表格可以看出,对于 N _cp指标,FACC-FMD算法在DIPCore、DIPFull和MIPS三个数据集上分别取得了第1、第1和第2的结果. 相对地,对于 N _cb指标,FACC-FMD算法在DIPCore、DIPFull和MIPS三个数据集上分别取得了第3、第3和第4的结果. 这说明FACC-FMD检测结果中有多个功能模块匹配到相同的标准功能模块,所以检测到的标准功能模块种类较少. 下面用具体的评价标准对FACC-FMD与其他算法比较.

图  3  DIPCore数据集上2种策略检测质量的比较

Figure  3.  Comparative result of algorithms for DIPCore data

下载: 全尺寸图片 幻灯片

图  4  DIPFull数据集上2种策略检测质量的比较

Figure  4.  Comparative result of algorithms for DIPFull data

下载: 全尺寸图片 幻灯片

图  5  MIPS数据集上2种策略检测质量的比较

Figure  5.  Comparative result of algorithms for MIPS data

下载: 全尺寸图片 幻灯片

表  3  5种算法在DIPCore数据集的实验结果

Table  3.  Experimental results of five algorithms in DIPCore data sets

算法	模块数	模块平均大小	N cp	N cb
FACC-FMD	500	9.06	311	216
MCODE	107	5.52	67	107
JERARACA	160	4.57	248	266
MCL	527	4.65	171	252
COACH	350	7.33	199	213

下载: 导出CSV 

| 显示表格

表  4  5种算法在DIPFull数据集的实验结果

Table  4.  Experimental results of five algorithms in DIPFull data sets

算法	模块数	模块平均大小	N cp	N cb
FACC-FMD	790	30.87	244	154
MCODE	70	13.11	20	36
JERARACA	1386	3.68	152	225
MCL	1204	4.24	196	248
COACH	1289	26.68	142	120

下载: 导出CSV 

| 显示表格

表  5  5种算法在MIPS数据集的实验结果

Table  5.  Experimental results of five algorithms in MIPS data sets

算法	模块数	模块平均大小	N cp	N cb
FACC-FMD	507	45.17	115	92
MCODE	63	8.33	25	46
JERARACA	1012	4.49	102	139
MCL	593	6.16	92	138
COACH	1387	17.14	289	156

下载: 导出CSV 

| 显示表格

5种算法的2组指标的实验对比如 图6~8所示. 在DIPCore数据集上,

图  6  5种算法在DIPCore数据集上的比较结果

Figure  6.  Comparative result of five algorithms for DIPCore data

下载: 全尺寸图片 幻灯片

图  7  5种算法在DIPFull数据集上的比较结果

Figure  7.  Comparative result of five algorithms for DIPFull data

下载: 全尺寸图片 幻灯片

图  8  5种算法在MIPS数据集上的比较结果

Figure  8.  Comparative result of five algorithms for MIPS data

下载: 全尺寸图片 幻灯片

FACC-FMD在精度、F度量和灵敏度指标上取得了最好的结果. 具体来说,FACC-FMD的精度是63.2%,比MCODE、JEARARCA、MCL和COACH分别高出0.6%、33.4%、30.8%和6.3%;F度量是55.7%,比MCODE、JEARARCA、MCL和COACH分别高出20.0%、16.4%、13.9%和2.6%;灵敏度是35.3%,比MCODE、JEARARCA、MCL和COACH分别高出18.4%、0.4%、1.5%和7.2%. 召回率、正的预测率和准确度分别位于第3、第4和第3. 在这3个指标上,JERARCA和MCL取得了最好的结果. 在DIPFull数据集上对比的结果类似,FACC-FMD的精度、F度量和灵敏度3个指标同样取得了最好的结果. 召回率、正的预测率和准确度都取得了第3的结果. 在MIPS数据集上,FACC-FMD的F度量取得了第2好的结果,灵敏度取得了最好的结果. 精度、召回率、正的预测率和准确度分别位于第3、第4、第5和第3. 通过这组实验可以看出,FACC-FMD在灵敏度这一指标上的表现很出色,说明FACC-FMD的检测结果对标准功能模块中的蛋白质具有较高的覆盖率. 这是因为FACC-FMD根据与核心组蛋白质的相似度进行聚类,也进一步证明了核心组蛋白质能够很好地标注一个功能模块. 同时,FACC-FMD在召回率上的表现不佳,造成该现象的主要原因是检测出的功能模块包含更多的蛋白质节点,使得 N _cb的值较小. 由于MIPS网络噪声数据较多,影响了检测质量,因此正的预测率在5个算法中最差. 综合3个数据集的检测结果能够得出,FACC-FMD与一些经典算法相比在多项性能指标上都取得了较好的结果.

4 结论

1) 本文提出了一种快速的基于蚁群聚类的PPI网络功能模块检测方法FACC-FMD. 该方法结合基因表达信息刻画蛋白质之间的共表达特性,抽取核心组蛋白质,并计算蛋白质的关键性,依据关键性对拾起放下进行严格的约束,降低了聚类过程的计算复杂度,并且不需要对初始聚类结果进行合并和过滤操作,大大地提升了蚁群聚类算法在功能模块检测问题上的时间性能. 同时,检测质量也有所提升.

2) 在多个PPI网络上的实验表明,FACC-FMD和一些经典算法相比在多项性能指标上也具有一定优势.