高通量技术的发展促进了大量蛋白质相互作用网络数据的产生,蛋白质相互作用网络决定了大部分细胞功能,对蛋白质相互作用网络进行研究有助于从系统角度理解各种生物学过程和生命活动规律,其中一项很重要且广泛的研究工作就是对蛋白质相互作用网络进行比对分析,通过网络比对可找到网络保守功能模块,对蛋白质功能进行研究,发现生物进化关系等。网络比对是一个NP-hard问题,蛋白质相互作用网络全局比对以最大化比对结果相似性的方式寻找蛋白质同源关系,难点在于如何将相似蛋白质进行匹配。研究表明蛋白质的序列相似性可用于判定蛋白质的同源关系,因此将其加入相似性计算过程有助于得到更多同源蛋白质,但是序列信息具有不完整性,因此,本文通过拓扑和序列结合的方式计算节点间的相似性指导比对结果的生成,具体工作内容如下:1、为寻找网络比对问题的近似最优解,整合基于离散化蝙蝠算法的网络比对算法Bat Align,分别在合成网络和真实网络中进行实验,与四种效果较好的算法进行对比实验,分别通过拓扑指标和生物指标衡量比对结果质量,并就比对结果中蛋白质功能进一步分析比对结果的生物学意义。实验结果表明,Bat Align算法能够得到生物质量高的比对结果,能够识别网络中的同源蛋白质。2、为提高比对结果拓扑和生物质量一致性,提出融合局部拓扑结构和序列信息的群体优化网络比对算法PONAL,在Bat Align算法的基础上进行几点改进。第一点,针对Bat Align过于依赖序列相似性问题,改进相似性计算方法,提高比对结果的拓扑质量;第二点,为丰富种群多样性并提高初始种群质量,更改初始种群的生成方法,保证每个节点的比对关系都是在相似性指导下得到的;第三点,使用保守边和保守节点相结合的目标函数,增加保守边数量的同时考虑保守节点的生物特性,提高比对结果的质量;第四点,为提高新个体的质量,使用全局搜索加局部随机搜索的方法。实验结果表明,PONAL算法能够识别网络中具有保守结构的子图,同时保证拓扑和生物质量一致性。3、为进一步提高比对质量,优化PONAL算法比对效率,提出基于集聚系数和序列信息的网络比对算法CCSNA。CCSNA算法分两步完成,第一步计算节点相似性,第二步使用搜索算法生成比对结果。在第一步中,首先,结合节点集聚系数和节点度计算节点重要性,然后结合节点重要性和节点序列信息计算节点初始相似性;在第二步中,计算了节点的相互作用得分,在初始相似性中加入相互作用得分得到比对相似性,贪心的选择比对相似性中得分最高的一对节点作为种子节点对并进行扩展,并增加其余邻居节点的比对相似性,增加邻居节点的比对概率,此种方法能够提高拓扑质量,根据更新后的比对相似性继续选择种子节点对并扩展,直到源网络所有节点完成比对。实验结果表明,CCSNA算法表现最佳,能够取得拓扑和生物质量高的比对结果。