智能优化算法及其在PPI网络中的应用研究

唐高阳

摘要：本文将围绕群智能优化算法的基本内容进行分析讨论，提出在PPI网络中群智能优化算法的具体应用路径，以布谷鸟搜索算法作为分析对象，切实保证聚类结果准确，借助网络形式更全面地反映蛋白质之间的关系，帮助科学家充分探究蛋白质的实际作用与功能，以此加强疾病防治效率，帮助人们保持身体健康，避免疾病造成严重危害。

关键词：PPI网络 蛋白质 群智能优化算法 布谷鸟搜索算法

Intelligent Optimization Algorithm and Its Application in PPI Network

TANG Gaoyang

（ShenYang Ligong Uiversity ， Liaoning，Shenyang Province， 110158 China）

Abstract： This paper will discuss the basic content of group intelligent optimization algorithm， put forward the specific application path of group intelligent optimization algorithm in PPI network， with cuckoo search algorithm as the analysis object， to ensure the accurate clustering results， with the form of more comprehensive reflect the relationship between protein， help scientists fully explore the actual role and function of protein， so as to strengthen the efficiency of disease prevention and control， help people maintain health and avoid serious harm from disease.

Key Words： PPI network; Protein; Group intelligent optimization algorithm; Cuckoo search algorithm

PPI是指蛋白質之间的相互作用，描述多个蛋白质分子利用非共价键形成复合体的过程，加强对PPI网络的研究不仅能实现疾病诊断的顺利开展，还能帮助人们更准确地认识到未知蛋白质的具体功能，明确分子机制，从而采取针对性的治疗手段。为了保证群智能优化算法在PPI网络中得到有效运用，首先要对其基本内容进行深入了解。

1群智能优化算法的基本内容

群智能是指昆虫的集体行为，通过将群居昆虫协作过程中反映的复杂行为特征作为研究基础，演化全新的算法技术。

1.1布谷鸟算法

布谷鸟算法的主要依据包括：布谷鸟繁殖行为，布谷鸟通常会将巢寄生作为主要繁殖方式，当其处在繁殖期时会积极找寻与自身孵化期相似、卵形相近的宿主，之后将卵寄放在宿主巢内，由其代替自己进行孵化;莱维飞行，属于随机行走的一部分，行走步长能够体现重尾的大致分布，行走过程中可以实现短距离探索。在运用智能优化算法时，可以借助莱维飞行进一步提升探索区域，保证种群多元化，达到全局最佳的目的。布谷鸟算法能够根据布谷鸟实际繁殖行为以及莱维飞行理论进行布谷鸟搜寻宿主巢的过程模拟，若想保证设计算法有效运用，还要达到以下3种理想状态：第一，布谷鸟每次只产下一个卵，依照随机择选的方式找寻窝来孵化;第二，在多个随机找寻的鸟窝中会将最优的一个会保留至下一代;第三，鸟窝数量基本恒定不变，将鸟窝实际主人发现外来鸟蛋的几率记为PA，其数值在0～1之间。在满足3种理想状态后，布谷鸟找寻路径与具体位置公式可记作：

= +a×Levy（λ）

其中 、 代表第i个鸟巢在m代以及m+1代时第j个位置，Levy（λ）表示Levy的飞行跳跃路径，其方向以及长度具有随机性。

布谷鸟算法的应用步骤可细分为：（1）首先要确立目标函数f（x），其中x=（x1，x2，x3……xd）T，之后进行群体初始化，最后随机生成多个鸟窝位置，即xi，并设置好位置参数;（2）计算鸟窝目标函数，记录最优解;（3）保留最优鸟窝位置，并依照 = +a×Levy（λ）公式进行其余鸟窝位置的更新;（4）进行当前鸟窝与上一代鸟窝的位置比对，若发现现有鸟窝更加优良便可记作最佳位置;（5）利用随机数R当作鸟窝实际主人发现布谷鸟鸟蛋的可能性，之后与PA进行对比，当出现R高于PA的状况，则需改变鸟窝现有位置，重新找寻鸟窝;（6）当未满足结束条件时，需要从第二个步骤开始重复操作;（7）完成全局最优1.2细菌觅食算法。

细菌的生存法则符合“优胜劣汰”的理论，若所处区域的食物相对丰富，便会进行分裂，形成全新个体，当所处环境较为恶劣，则细菌会进行迁徙，甚至选择死亡。以大肠杆菌为例，该细菌主要通过鞭毛进行游动以此获取食物，当细菌所在区域食物稀缺时，便会随机选择方向进行游动，若发现新环境食物足够满足自身生存需要，便会持续游动至步数阀值。细菌觅食算法最初是由Passino科学家以大肠杆菌的吞噬行为作为依据，提出的仿生算法，该算法的操作步骤可细化为以下3点。

1.1.1趋向性操作

趋向性操作是指细菌向营养丰富的区域移动的行为，在此过程中，细菌主要是依靠游动或者旋转实现聚集，若细菌在旋转后所处的环境得到显著改善便会停止移动，反之则会重新选择方向进行移动，直到环境能够满足其生存需求，亦或是达到移动步数临界点。

1.1.2复制操作

复制操作主要是指在食物相对丰富的区域内，细菌的生命周期结束或者达到临界趋化值，将进行繁殖行为，细菌所采取的繁殖方式为分裂，能够形成与自身觅食能力完全一致的新个体，在分裂时需要与细菌本身的适应值累加和作为判断标准，如果觅食能力不佳，低于平均水平便会有半數细菌死亡，而觅食能力较强的半数细菌则会进行复制操作，以及提升营养环境的搜寻速度。

1.1.3迁徙操作

迁徙操作是指细菌所处的环境食物相对匮乏，或者环境正朝着劣化的方向发展，此时细菌个体随时可能面临死亡的风险，因此细菌为了继续生存繁殖，会选择生成一个全新个体，借助迁徙操作生成的个体更加趋近于全局最优解，这样便可有效避免局部最优解的产生[1]。

2 PPI网络中群智能优化算法的应用路径分析

PPI网络本身属于真实网络，与传统的规则网络以及随机网络不同，其结构组成更为复杂，可以定义为无向简单图，主要由顶点集与边集组成，边集中的每条边都有相应的顶点，并且顶点可以表示网络中的真实个体，而每条边则代表一对个体存在的相互作用，在蛋白质网络中，每个顶点都可作为一个个体蛋白质，并且随着对网络拓扑结构深入分析，人们逐渐发现复杂网络中存在模块化结构，且每个模块都存在结点连接。除此之外，PPI网络还具有以下2种特征：一是小世界网络，该特性是由WATTS科学家首次提出，通过以k阶规则网络作为分析基础，依照一定概率完成端点断开，在重新连接后新的端点能够从网络中任意结点被随机选择，当网络属于规则网络时，概率为0，如果网络属于随机网络则概率为1;二是无尺度属性，该特征是由barabasi科学家最先发现，主要体现在真实网络结点度满足幂率分布规律时，当度的结点概率小于k-r时，证明网络结点度相对较小，但存在的部分结点度仍高于网络的平均水平，此时这些具有大量连接的结点可定义为集散结点，由其组成的网络即可成为无尺度网络。

在20世纪末，群智能算法得到大范围推广，比如蚁群算法、遗传算法等，这些算法都是借助模拟生物行为或者部分自然现象来实现问题的最优化处理，这种方法也是近年来算法设计与分析领域中的热点课题。为了确保PPI网络中群智能优化算法的应用的科学、合理，能够保持良好的适用性与可行性，本文将以布谷鸟算法作为研究对象，该算法本身具有高效、操作便捷的优势，并且随机选取的路径均为最优解。

2.1涉及知识

2.1.1蛋白质结点相同之处

在PPI网络当中，需要采用一个a行、b列的向量元素Xab用于表示a个蛋白质与b个蛋白质之间存在的相互作用，并且向量Xab中的各项参数能够表示不同蛋白质之间的作用大小，若蛋白质之间切实存在相互作用，则作用大小可定义为权重值，如果蛋白质之间属于彼此孤立存在的状态，不存在相互作用，则权重值为0。由于不同蛋白质之间的定义过于多样化，为了更好地实现区分，需要使用相似度衡量标准进行相似性判断，其具体内容为：

Bader法：Sab=Xab2/（Xaa×Xbb）

Dice法：Sab=2Xab/（Xaa+Xbb）

Simpson法：Sab=Xab/min（Xaa，Xbb）

Bridge法：Sab=1/2×（Xab/Xaa+Xab/Xbb）

Jaccard法：Sab=Xab/（Xab+Xbb-Xaa）

其中Xab代表蛋白质a与蛋白质b的相似度，而Xab则代表Xa与Xb的乘积。在本次实验当中，需要充分结合上述提出的相似度定义，并进一步提出演化推算后的新相似度定义，其表达式为：

Dab=（Xab-Xaa）×（Xab-Xbb）/Xab×Xbb

Sab=1-Dab

之后将上述2个公式进行简化可得出

Sab=Xab（Xab+Xbb-Xaa）/（Xaa×Xbb）

其中Sab表示结点a处的周边结点结合，之后要验证其数值是否介于0～1之间。证明过程为：Xaa本质意义属于结点a的周边个数，因此Xbb也可理解为结点b周边个数，而Xab则代表结点a与b的交集数量。因此Xaa-Xab必然高于0，并且Xbb-Xab的数值也处在0～Xbb之间，而（Xab-Xaa）×（Xab-Xbb）的值则低于Xaa×Xbb，可以确定Dab的值处在0～1之间，之后根据公式Sab=1-Dab可知，Sab同样处于0～1之间。因此可以将Dab作为衡量PPI网络中的结点距离标准[2]。

2.1.2目标函数

在PPI网络中结点K的定义主要表示与蛋白质结点的连接边数量，而结点的加权度则表示该蛋白质结点相连的全部边权重总和。结点加权聚集度代表与结点相连的任意两个结点的权重和，具体公式为：

WKv= wuk

其中WKv代表结点加权度。而结点的加权聚集系数WCv则需根据以下公式进行计算：

WCv=2×WKv/Kv×（Kv-1）

由此可知，网络综合特征值需要根据以上两种公式结合计算，即：

Valuev=a×WCv+（1-a）×WKv/N

其中，u、k代表与蛋白质相连的任意2个结点，并且u、k之间存在边，Wuk表示边的实际权重值，a则代表0～1之间的随机变量，通常取0.5。N表示PPI中的结点个数。以上3个公式能够证明网络特征值可以充分反映不同结点之间的连接强度，同时也能体现结点局部区域的连接密度，为了确保结点特征得到更准确地描述，需要进一步引入加权度，其公式为：

WDv= wuk

Valuev=a×WCv+（1-a）×WDv/N

其中u属于结点v的相邻结点，Wuv是指两结点边的权重，而WDv则表示结点v的实际加权度。在带权中的PPI作用网络下，网络的特征值可以从形态或组成上看出，不仅需要将模块中不同蛋白质的连接关系进行全面考虑，还要充分掌握彼此之间的连接权度值，利用随机变量实现比重调节，因此用以衡量PPI网络聚类结果的目标函数可表示为：

fitc=  value（j）/n

其中c表示聚类结果中的任意模块，n代表蛋白质个数，fitc是指网络综合特征数值，其数值越高，证明聚类结果越优良。

2.2算法描述

2.2.1處理数据、选取中心点

为了确保数据得到预先处理，需要将蛋白质名称与数字相互对应，为蛋白质赋予代码编号，这样便可在运行程序时更便捷地开展数据比较与计算，以此达到提升算法运行速度与运行效率的目的。在初始化聚类中心时，要依照网络结点与边所蕴含的信息，使利用度与特征值阀值能够选择最优的中心点。若某结点度与特征值高于给定阀值，则此结点需要记作聚类中心。同时为了进一步提高收敛速度，实现种群多元化，还要提前择选a组聚类中心，保证每组聚类中心具有一定的差异性，但组件可以实现聚类中心的重合[3]。

2.2.2算法步骤

首先，数据处理需要依照度与特征值阀值完成聚类中心的候选，初始化记作cluster，参数度阀值设置为threshold，特征值阀值记作com-threshold，相似度阀值则为sim-threshold，最大迭代次数为maxter，而访问表示则为visit。其次，要根据莱维飞行从候选聚类中心中随机选出a组鸟窝，要求每组包含b个聚类中心，如果两组鸟窝数量一致，则需在整体中重新选取，进行重叠组的替代。之后依照相似度对a组鸟窝进行聚类处理，从而获得a组的聚类结果。最后，要将a组聚类结果以及初始化数值依照适应度值进行排列，记录最优一组，将其作为cluster。同时要使用各组适应值最高的模块以及cluster中适应度最小的聚类中心进行比较，若二者一致，则使用适应值加高的模块进行替换，若聚类中心不一致，则使用适应度最小的模块进行代替，并保留最优聚类结果至下一代。此外，要遵循t=t+1的计算原则，若t小于最大迭代次数，则从聚类结果的计算重新开始推演算法，若t高于最大迭代次数，则输出最优解cluster，并进行结果评价[4]。

2.2.3聚类过程

第一，在聚类开始阶段需要依照聚类中心层层递进的原则进行比较，与传统的统一集中比较不同，分层开展的方式能够更好地保证聚类结果的准确性，降低误差的形成几率。第二，由于鸟窝的数量属于恒定不变，因此需要在实现聚类时将周边结点以及中心点进行适当调整，使其满足相似度阀值，同时要取消中心点作为聚类中心的权限，并从候选中心中择选未曾访问过的结点，确保该结点与原聚类中心不存在重叠关系，能够有效填补空缺。第三，各组聚类结果需要依次实现与最优组的结果对比，判断聚类中心是否为最优组的成员之一，如果是，则找出其所在位置记作loc，反之，则将其与排序后的元素进行比对[5]。

2.3性能探究与仿真实验

布谷鸟算法的代价都线性主要体现在结点数上，最差状况表现为无噪声点，要求对PPI网络中的各个结点都采取遍历处理。该算法的主要优势可细分为：（1）中心点选取更加高效、准确，能够充分符合PPI网络的小世界特征，所选择的中心点都较大，具有无尺度特点，在将其作为中心聚类的过程中主要依照厂度实现优先遍历，以此达到防止全部结点都与中心点完成比较付出过大代价的目的;（2）在完成遍历时，需要将其与未访问的中心点记作普通中心点，当满足预定阀值后，将其归属到相应类当中，防止后期模块合并产生不必要的消耗[6]。

3 结语

综上所述，通过对群智能优化算法的基本内容进行分析讨论，提出PPI网络中群智能优化算法的具体应用路径，以此充分发挥该算法的概率搜索作用，准确完成目标函数的输出，确保大量数据得到及时处理，更好地为生物研究提供切实可行的参考对象。

参考文献

[1]胡健，朱海湾，毛伊敏.基于时序加权PPI网络的关键蛋白质识别[J].计算机工程与应用，2019，55（23）：150-162.

[2]杨书新，鲁纪华，汤达荣.基于动态加权PPI网络的关键蛋白质识别算法[J].计算机应用研究，2019，36（2）：367-370，379.

[3]杨书佺，舒勤，何川.改进的果蝇算法及其在PPI网络中的应用[J].计算机应用与软件，2020，31（12）：291-294.

[4]雷秀娟，黄旭，吴爽.基于连接强度的PPI网络蚁群优化聚类算法[J].电子学报，2020，40（4）：695-702.

[5]唐家琪，吴璟莉.基于PPI网络与机器学习的蛋白质功能预测方法[J].计算机应用，2020，38（3）：722-727.

[6]胡庆生，雷秀娟.PPI网络的改进马尔科夫聚类算法[J].计算机科学，2020，42（7）：108-113.

sdjzdx202203231615