基于人工蜂群繁殖机制的PPI网络聚类方法

摘要

本发明公开了一种基于人工蜂群繁殖机制的PPI网络聚类方法，具体包括如下步骤：将PPI网络转化为无向加权图；参数设置；对PPI网络的每个结点和边预处理；计算所有结点的加权网络综合特征值；初始化蜂后；婚飞过程；幼蜂的局部搜索；蜂后的选优；计算当前适应度并比较，直到输出全局最优聚类结果。该方法不需要预先设定聚类个数，在聚类过程中能够自动得到，避免了人为设定聚类个数的主观性，且时间复杂度降低明显。采用MIPS数据库做实验仿真，结果比较接近标准数据库且在正确率、查全率和运行时间等指标上性能较优。与其他的聚类方法相比，该方法采用基于繁殖机制人工蜂群方法机理，能自动确定聚类个数，实现聚类过程，有效提高了聚类效果和计算效率。

主权项

一种基于人工蜂群繁殖机制的PPI网络聚类方法，其特征在于，具体包括如下步骤：1)将PPI网络转化为一个无向加权图：将PPI网络转化成一个无向加权图G(V，E)，其中，V＝{v_i,i＝1,2,…,n}为结点v_i的集合，E为边e的集合，结点v_i表示蛋白质，边e表示蛋白质之间的相互作用，w_ij表示结点v_i和结点v_j之间相互作用的大小，也就是结点v_i和结点v_j之间边e_ij的权值，若v_i和v_j之间没有边则w_ij＝0，i＝1,2,…,n，j＝1,2,…,n；2)参数设置：令count，maxcount分别表示控制外循环的当前迭代次数和外循环对应的最大迭代次数，maxcount∈[10,1000]，并令count＝1；iter，maxiter分别表示控制内循环的当前迭代次数和内循环对应的最大迭代次数，maxiter∈[10,200]；N和S分别表示蜂后婚飞时的能量和速度，N∈[50,1000]，S∈[10,500]；fval，gfval分别表示当前适应度和全局最优适应度，令gfval＝∞；cluster，gcluster分别表示当前的聚类结果和全局最优聚类结果；visited是结点被访问标记；n表示蛋白质结点个数，T表示蜂后与雄蜂交配成功的计数器；3)对PPI网络的每个结点v_i和每个边e进行预处理：所述对结点v_i预处理是计算结点v_i的加权网络综合特征值com‑value_i；所述对边e预处理是计算改进的边聚集系数CC_i,j；4)计算所有结点的加权网络综合特征值com‑value_i的代数平均值Av‑com‑value，将大于Av‑com‑value*W的结点保存，其中W∈[0.5,2]；5)初始化蜂后：令iter＝1，蜂后代表聚类中心，初始化蜂后就是确定第一个聚类中心，从大于Av‑com‑value*W的结点中随机选取一个结点作为第一个蜂后，并令该蜂后结点的visited＝1；6)婚飞过程：给蜂后的能量和速度赋初值，令N＝100，S＝50，令蜂后与雄蜂交配成功的计数器T＝0，将与蜂后结点的改进的边的聚集系数CC_i,j大于零的结点作为要与蜂后交配的雄蜂，将所有雄蜂结点按照该雄蜂结点与蜂后结点的改进的边的聚集系数CC_i,j降序排列，排序后的雄蜂依次与蜂后交配，每交配成功一次，蜂后的速度S和能量N就以式10和式11衰减一次；通过式9计算每个雄蜂结点与蜂后结点的交配成功概率P(i)，同时生成一个[0,1]之间的随机数rand，若P(i)>rand，则交配成功，将该雄蜂的精子加入蜂后的受精囊中，并将该雄蜂结点的访问标记visited修改为1，计数器T＝T+1；交配失败则继续与下一个雄蜂交配，直至蜂后的能量N小于能量阈值Thred∈[0.01,0.99]或者蜂后的受精囊中的精子数量大于M∈[20,200]，一次婚飞过程结束；进入幼蜂的局部搜索过程；P(i)＝exp[‑Δ(f)/S(t)]        式                              9其中，P(i)表示雄蜂结点v_i和蜂后交配成功的概率；‑Δ(f)表示雄蜂结点v_i和蜂后结点加权网络综合特征值com‑value_i的差值；S(t)是蜂后在时刻t的速度S；蜂后的速度S和能量E以式10和式11的方式衰减：S(t+1)＝α*S(t)             式10N(t+1)＝N(t)‑β*N(t)/M          式11其中，β*N(t)/M是每次转移后能量的消耗量；β∈[0.5,2]为能量衰减因子；E(t)表示当前蜂后的能量，E(t+1)表示与一个雄蜂交配后的蜂后的能量；S(t+1)表示与一个雄蜂交配后的蜂后的速度；M表示受精囊大小，α∈[0,1]为每次速度的衰减因子；7)幼蜂的局部搜索过程：将蜂后受精囊中每个精子结点的邻接点中结点加权网络综合特征值com‑value_i最大的结点保存下来，作为发育优良的幼蜂结点；8)蜂后的选优过程：从发育优良的幼蜂结点中选取结点加权网络综合特征值com‑value_i最大的结点作为新的蜂后结点，从而更新了聚类中心；9)iter＝iter+1，如果iter<＝maxiter，并返回步骤6)，否则，转向步骤10)；10)计算当前适应度fval；若当前适应度fval<gfval，则令gcluster＝cluster，gfval＝fval；否则gcluster和gfval不变；11)count＝count+1，如果count<＝maxcount，并令所有结点的访问标记visited＝0，并返回步骤4)，否则，输出全局最优聚类结果gcluster。