蛋白质是生物体的重要组成部分,也是生命的物质基础,参与和控制了生物体内的大部分生命活动。蛋白质在生命体中并不是单独存在的,而是通过蛋白质之间的相互作用关系来实现生命体的具体功能。随着高通量实验方法的发展,可获得的蛋白质相互作用(Protein-protein Interaction,PPI)网络数据逐渐增多,为系统地研究蛋白质之间的相互作用关系,进而识别网络中有重要意义的功能模块和关键蛋白质提供了可能。在PPI网络基础上研究功能模块和关键蛋白质不仅可以促进生命科学的研究,而且在疾病诊治和药物靶细胞设计等方面都具有重要的应用价值。本文对PPI网络中的分析算法进行研究,在深入分析网络层次结构的基础上,主要致力于PPI网络中的功能模块挖掘以及关键蛋白质的预测等研究,具体内容包括以下三个方面:(1)提出了基于PPI网络层次结构划分的功能模块挖掘算法FM-HS。该方法首先使用遗传算法找到一棵与PPI网络相对应的具有最大似然的层次结构树,然后通过对该树进行层次划分得到若干功能模块,最后根据模块度的值选择最佳的划分方案;同时,通过节点间在树中的公共祖先信息可以得到它们存在相互作用的可能性。该方法在挖掘功能模块的同时还可以对蛋白质之间的相互作用进行预测。通过在标准数据集上进行实验,结果表明本文提出的FM-HS算法能够更加准确地挖掘出PPI网络中的功能模块。(2)提出了基于Markov随机游走的关键蛋白质识别算法EPM。该方法同时考虑了生物信息和网络拓扑结构信息,进而克服了数据噪声高带来的负面影响。EPM使用Markov随机游走的思想:首先对PPI网络中的每一个顶点赋予表示其重要程度的得分,所有顶点的得分构成了一个n列的向量,给出其初始分值;然后根据一定的概率让分值在网络中随机游走并在传递中进行修改;最终按分值由大到小排列,输出分值最大的k个蛋白质即为关键蛋白质。在标准数据集上的实验结果表明,本文提出的EPM算法能够更加准确地识别较多的关键蛋白质。(3)提出了在PPI网络中基于遗传算法的关键蛋白质识别算法EPGA。该算法选取m个初始个体,每个个体由P个蛋白质组成,通过遗传算法对top-P个蛋白质的关键性进行整体度量,选取关键性最高(即最大适应度函数值)的个体,最后对个体解进行局部优化。在适应度函数中,本文融入了基因表达数据和域交互程度等多源生物信息,而且考虑到了蛋白质的二阶邻居对蛋白质关键性的影响。在标准数据集上的实验也表明,实验结果与其他经典算法相比,本文提出的EPGA算法识别关键蛋白质的准确率更高。