近似图匹配广泛应用于社交分析、情报学、生物信息学等领域,是当前研究的主流方向。由于受噪声的制约,传统的近似算法无法高效地对近似图匹配问题进行求解,尤其是近似子图匹配问题。采用统计显著性模型是缓解乃至克服噪音问题的一种可行策略。全局网络比对问题是生物信息学中热门的研究领域之一,通过网络比对侦测功能相似性蛋白质和发现不同物种之间蛋白质同源关系等具有重要意义。全局网络比对的目标是在两个网络之间找出最佳全局的比对,通过适当描述,可将全局网络比对问题转化为近似图匹配问题。本文以图论和统计显著性模型为基础,对近似子图匹配问题进行了研究和探索;在此基础上,对全局网络比对问题进行了研究。论文主要工作包括:(1)对近似子图匹配问题进行了研究。针对近似子图匹配算法忽略查询图标签信息和待搜索大型数据图标签信息之间存在“潜在分布”关系的问题,提出一种基于卡方统计量捕获的统计显著性来表征近似子图结构匹配相似度的方法,其中统计显著性在处理噪音时具有鲁棒性,并能够充分考虑节点邻域的内在结构和标签信息之间存在“潜在分布”的关系。通过与传统算法作对比实验,表明算法效果较好,运算效率较高。(2)基于破坏性等价于重要性对全局网络比对问题进行了研究。针对现有的全局网络比对算法缺乏对false hub蛋白质和致命性hub蛋白质在结构和性质上差异的考虑,提出了一种基于“破坏性等价于重要性”的思路,根据破坏远近不同的节点给网络整体连通状况所带来的损失来度量蛋白质结构重要性的方法。对比其他最新、最流行的算法表现出更高的比对精确度和保持功能一致性。(3)基于统计显著性对全局网络比对问题进行了研究。针对PPI网络数据存在大量噪音的事实,结合统计显著性模型,提出一种基于卡方统计的全局网络比对算法。对几个真实的数据集进行了大量的实验,结果表明本文提出的算法在比对结果精确度和运算效率上要优于部分最先进的算法。