1.基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,包括:步骤1:获取输入比对网络和序列相似性信息;
步骤2:对输入比对网络和序列相似性信息进行处理后,构建候选簇集合;
步骤3:采用模拟退火算法,在候选簇集合中随机选取一个候选簇进行迭代后加入候选簇集合,并根据加入候选簇前后比对的目标函数得分的差值判断是否接受新比对结果;
步骤4:若目标函数得分差值大于零,则无条件接受新比对结果;若目标函数得分差值小于零,则计算接受当前比对的概率;
步骤5:判断是否达到模拟退火算法的退火终止条件,是,则结束比对,输出比对结果,否则返回至步骤3。
2.根据权利要求1所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述步骤2中,所述对输入比对网络和序列相似性信息进行处理过程包括:对两个节点相关的最大序列相似性得分进行归一化,归一化计算公式为:其中,w(u,v)为节点u和节点v之间的序列相似性得分,wmax(u)为与节点u相关的序列相似性得分中的最大值,wmax(v)为与节点v相关的序列相似性得分中的最大值。
3.根据权利要求2所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述步骤2中,所述对输入比对网络和序列相似性信息进行处理过程还包括:对于某一条边,若其边的得分小于相应边的阈值,则删除这条边,过滤的计算公式为:w(u,v)<β×max(u,v)其中,β为用户设定的参数,取值在0到1之间;max(u,v)为与节点u或节点v相关连的序列相似性得分的最大值。
4.根据权利要求1所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述步骤2中,所述构建候选簇集合包括:通过构建序列相似性加权k‑部图S并通过相似图S搜索加权最大k团构建候选簇集合,所述搜索加权最大k团采用分支限界法进行搜索,按广度优先策略搜索问题的解空间树,解空间树中任意一层i中的节点数为i+1,搜索的上界计算公式如下:
其中,wmax(u,r)表示节点u与图s中节点r之间最大的序列得分权重,EW(s)表示该分支所有节点的权重之和的最大值,PWmax(Ns)表示该分支所有节点在图S中的邻居节点的最大权重和,Rep(Nll)表示在节点η的邻居节点中存在于序列相似图S中的节点集合,当且仅当该分支所有节点的潜在权重之和超过该分支计算的最大值时,选择该分支,将该节点加入簇中,继续扩展下一个节点。
5.根据权利要求1所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,采用模拟退火算法,在候选簇集合中随机选取一个候选簇进行迭代后加入候选簇集合,并根据加入候选簇前后比对的目标函数得分的差值判断是否接受新比对结果的方法为:a、模拟退火算法初始以一个空比对开始,第一次迭代时,在候选簇中选择权重最大的团作为第一个比对;
b、在其后的每一迭代中,将上一轮迭代的候选簇作为种子,在多蛋白质相互作用网络中对该种子中节点的邻居节点进行扩展,将以种子节点的邻居节点为中心生成的候选簇加入本轮迭代的候选簇集合NG中;
c、进行降温步骤后,在上一步生成的候选簇集合NG中随机选取一个候选簇,并计算加入这个候选簇后当前比对的目标函数得分;
d、若新比对与上一次迭代产生的比对的目标函数得分差值大于零,则无条件接受新比对结果;若两次比对之间的目标函数差值小于零,则根据Metropolis准则计算接受当前比对的概率,在0到1之间取一个任意值,若任意值小于接受当前对比的概率则接受产生的新比对,否则进入下一次循环,一直循环算法到温度降至最小值为止。
6.根据权利要求1所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述步骤3中,在候选簇集合中随机选取一个候选簇进行迭代后加入候选簇集合时,当候选簇中的节点与已比对上的节点簇集合之间满足 时,将候选簇加入比对簇集合;其中,c={v1,v2,…,vl}为每一次迭代过程中选择的候选簇,l≤k,k为迭代次数,Cl={cl1,cl2,…,cln}为已比对上的节点簇集合。
7.根据权利要求1所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述步骤3中,在候选簇集合中随机选取一个候选簇进行迭代后加入候选簇集合时,当候选簇节点与已比对上的节点簇集合重叠的节点满足:|c∩Cl|=|c|,则表示当前迭代选择的候选簇都表示已经比对,则不考虑这个候选簇的节点。
8.根据权利要求1述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述步骤3中,在候选簇集合中随机选取一个候选簇进行迭代后加入候选簇集合时,对于已比对上的节点簇集合中任意一个节点簇cli∈Cl,满足: 则将候选簇中未重复的节点与其在同一个网络中的节点进行替换,通过局部扰动产生一个新的状态解。
9.根据权利要求1所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述步骤3中,在候选簇集合中随机选取一个候选簇进行迭代后加入候选簇集合时,当候选簇节点与已比对上的节点簇集合重叠的节点满足: 则将候选簇中的重复节点移除,并将剩余节点构成的簇加入候选簇中,以便进行下一次迭代搜索。
10.根据权利要求1所述的基于模拟退火的多蛋白质相互作用网络比对方法,其特征在于,所述目标函数计算公式如下:
AS(A)=α×CIQ(A)+(1‑α)ICQ(A)其中,参数α是控制目标函数中拓扑和序列信息所占比重的参数,CIQ为衡量簇间节点的拓扑质量的指标,计算公式如下:
其中, 表示节点分别在簇Clm,Cln内的边的集合,cs(m,n)得分表示任意两个簇Clm,Cln中保守边的网络所占比例,计算如下:其中,sm,n表示任意两个簇Clm,Cln中所包含的节点所涉及的网络数,s’m,n表示 中包含的边所涉及的网络数,当s′m,n=1时,cs(m,n)=0,表示在两个簇之间没有保守的相互作用;
其中,E(Cli)表示在图s中与簇Cli中节点相连的边的集合,wmax(u)表示与节点u相连的边权重的最大值,w(u,v)表示节点u和节点v之间的序列相似性得分。