用于相互作用检测的高通量生物实验方法的技术进步导致了蛋白质相互作用数据的爆炸式增长,这些数据对不同物种间的生物关系分析将具有重要意义。蛋白质相互作用数据往往被抽象为一个网络,网络比对算法则是进行网络数据分析的重要工具,通过对两个不同物种进行网络比对,将有助于理解细胞组织,发现物种间的进化保守关系和个体差异,从而有助于进行疾病分析、新药靶点治疗和为物种间的注释转移提供重要信息等。目前从实验中提取的蛋白质相互作用网络存在数据缺失或数据噪声问题,其次现有算法目标函数中包含的拓扑信息也比较单一,这严重影响了算法的比对质量,另外,基于模块化的网络比对算法在模块相似性计算方面往往以枚举方式进行,增加了算法的时间复杂度。本文针对以上不足展开研究,主要内容如下:1.为解决真实蛋白质相互作用网络部分数据缺失和噪声问题,提出了一种状态转移和邻居加权的成对蛋白质相互作用网络比对算法。算法首先介绍了马尔可夫链和Page Rank的工作原理;其次使用了孤立结点概率平分策略和使用阻尼因子增加随机比对概率的方法来补充相似性矩阵,并据此使用马尔可夫链迭代更新状态转移向量,直至收敛;最后根据状态转移向量获取结点间的相似性矩阵,并使用邻居加权的贪心算法求解网络比对问题。实验结果表明,该方法生物质量最佳,且运行时间较短。2.为解决目标函数中拓扑信息单一问题,提出了一种融合多种拓扑信息的成对蛋白质相互作用网络比对算法。算法首先提出了相关值的概念,结合网络自身结构信息来衡量同一网络中结点间的相似性;其次为了更充分地挖掘不同网络结点间的相似性信息,提出了一种基于特征向量中心性的拓扑得分计算方法,该方法融合了度信息,结点自身的特征向量中心性信息以及邻居结点的平均特征向量中心性信息,并根据这些信息得出的相似性得分进行模块内比对;最后考虑到网络的模块化性质,引入了模块间保守边度量,以便能最大限度的获取不同网络模块间的边保守信息。实验结果表明,该算法获得了更高拓扑质量的比对,同时与现有的其他方法相比,该方法的综合表现最好。3.为进一步提高比对质量,减少模块相似性计算的时间复杂度,优化比对效率,提出了一种基于分解与整合策略的成对蛋白质相互作用网络比对算法。算法整体上采用了分解与整合策略进行比对。首先进行模块划分,并根据已有的比对信息计算模块相似性;然后根据模块间结点的子比对获取候选结果集,最终通过超图匹配获得比对结果。对于不同网络间结点的相似性,分别从结点自身和结点间的差异进行相似性判断。使用已有的比对信息的集体行为预估模块间的相似性,大大提高了模块匹配的效率。基于相关值和结点的得分函数保证了模块内结点的相似性。实验结果表明,该算法在生物和拓扑指标上均表现最佳,达到了拓扑与生物功能质量的平衡。