生物分子网络拓扑结构比对的自适应方法

摘要

本发明涉及一种生物分子网络拓扑结构比对的自适应方法。该方法用于寻找两个生物分子网络生物学意义上的最优映射，其步骤如下：A、构建第一生物分子网络和第二生物分子网络的初始相似矩阵 。B、基于相似矩阵，获得第一生物分子网络中的节点和第二生物分子网络之间的比对映射矩阵。C、根据当前迭代步的匹配结果，自适应地更新相似矩阵，然后计算得到下一迭代步生物分子的相似矩阵。D、计算每一迭代步的映射矩阵的得分，然后判断是否结束计算。其特点在于针对节点的网络拓扑特点自适应地计算网络节点之间的相似性，有效降低仅用匈牙利算法而需要的大量计算时间，同时提高仅用贪心算法的准确率，从而找出比同类算法更好的映射。

主权项

生物分子网络拓扑结构比对的自适应方法，其特征在于该方法的具体操作步骤如下：a.构建两个分子网络的初始相似矩阵S⁰，该两个分子网络分别记为第一生物分子网络G_A和第二生物分子网络G_B，所述的初始相似矩阵S⁰中的S⁰(a_i,b_j)表示节点a_i和节点b_i之间的相似系数，其中a_i∈G_A，b_j∈G_B a_i表示第一生物分子网络G_A中的节点，b_j表示第二生物分子网络G_B中的节点；b.根据当前迭代步的相似矩阵S^k，使用匈牙利算法、贪心算法对第一生物分子网络G_A中的节点和第二生物分子网络G_B中的节点进行匹配，获得G_A中的节点和G_B中的节点之间的映射矩阵M^k，其中k表示迭代步数，初始时k＝0：其中每一个元素M^k(a_i,b_j)为1或0，1表示节点a_i和节点b_i匹配，0则表示不匹配；c.根据步骤b所得的映射矩阵M^k，使用节点的邻居节点之间的相似性，自适应地更新相似矩阵S^k，然后结合生物分子的初始生物相似性和生物分子在各自网络中的拓扑相似特征，计算得到下一生物分子的相似矩阵S^k+1；d.计算每一迭代步的映射矩阵M^k的得分SS^k，然后计算生物分子的相似矩阵S^k+1和S^k之间对应元素差值的绝对值，判断是否结束迭代计算，若生物分子的相似矩阵S^k+1和S^k之间对应元素的差值的绝对值的最大值小于阈值λ，λ为允许的计算误差，则结束计算，取第m，0≤m≤k步的映射矩阵M^m为最终映射结果，其中m需满足该步的映射矩阵M^m的得分SS^m最大；否则，若生物分子的相似矩阵S^k+1和S^k之间对应元素的差值的绝对值的最大值不小于阈值λ，则不结束计算，返回步骤b到步骤d继续进行计算，直到前后两次生物分子的相似矩阵S^k+1和S^k之间对应元素的差值的绝对值的最大值小于阈值λ，则结束计算。