1.一种基于遗传算法的生物网络比对方法,其特征在于,包括以下步骤:步骤1:读取源网络、目标网络数据文件及其序列相似性得分文件;
步骤2:计算源网络、目标网络中节点的重要性得分,结合网络的拓扑相似性和序列相似性得分计算节点对相似性得分;
步骤3:基于节点对相似性得分初始化种群;
步骤4:计算种群中个体的适应度值;
步骤5:选择、交叉产生下一代;
步骤6:重复步骤4、步骤5直至目标函数收敛或迭代次数达到阈值;
其中:采用最小度启发式算法计算节点的重要性得分,包括如下步骤:初始化网络Gi(i=1,2)中每个节点和边的权重,边的初始权重w(u,v)设为1,节点的初始权重w(u)设为0:
其中u,v表示网络Gi中的节点,Ei表示网络Gi中边的集合;
从度为1的节点开始,到度为10的节点结束,删除当前度最小的节点u,并更新其相邻节点和边的权重,当一个节点被移除时,它的邻接边也相应移除,移除的节点和边的权重被分配给它们的邻居节点和边;
当|N(u)|为1时:
当|N(u)|大于1时:
其中N(u)表示节点u的邻居节点集合,|N(u)|表示节点u的邻居节点个数;
计算节点v的重要性得分IS(v):
其中,IS(v)表示节点v的重要性得分,λ控制节点和边的权重,取0.4;
对节点v的重要性得分进行归一化处理:IS(v)=IS(v)/maxv∈V{IS(v)};
结合网络的拓扑相似性和序列相似性得分计算节点对相似性得分,对于网络G1中的节点u和网络G2中的节点v,计算节点对(u,v)的相似性得分:
其中控制节点对拓扑相似性得分和序列相似性得分的权重,B(u,v)表示节点对(u,v)的归一化bit-score值,即从输入的序列相似性得分文件中读取相应数值并进行归一化处理;
所述初始化种群包括以下步骤:两个网络中的任意节点对按照相似性得分S从大到小排列,通过贪心算法选择当前相似性得分最高的节点对,直到G1网络中的每个节点都被比对上;随机产生p-1个比对结果;
所述种群个体适应度值即网络比对的目标函数:由节点对的相似性得分和边正确性得分构成:
其中,A表示一个比对结果,F(A)表示比对结果A的目标函数得分,S(u,v)表示节点对(u,v)的相似性得分。
2.如权利要求1所述的基于遗传算法的生物网络比对方法,其特征在于,在种群中选择的过程包括:在迭代的过程中控制种群数目p固定,且p为偶数,为保证在迭代的过程中种群的质量并且加快种群的收敛速度:NABG保留种群前50%的结果至下一代,并选择上一代种群的第i(0≤i
3.如权利要求2所述的基于遗传算法的生物网络比对方法,其特征在于,所述交叉的过程为:经过选择阶段选出父代个体后,利用Knuths正则分解和循环分解算法保证两个父代个体交叉产生一个子代个体,并且子代个体可以继承两个父代个体各一半的特性。
4.一种计算机设备,包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序,其特征在于,所述处理器执行所述程序时实现权利要求1到3任一项所述方法的步骤。
5.一种计算机可读存储介质,其上存储有计算机程序,其特征在于,该程序被处理器执行时实现权利要求1到3任一项所述方法的步骤。
6.一种处理器,其特征在于,所述处理器用于运行程序,其中,所述程序运行时执行权利要求1到3任一项所述的方法。