● 摘要
随着人类基因组计划的完成以及生物信息技术的发展和海量生物数据的飞速增长，蛋白质相互作用(protein-protein interaction， PPI)网络这个研究课题应运而生。蛋白质不是孤立的，而是通过相互之间有着紧密的联系完成各种功能。对蛋白质相互作用网络的聚类有利于疾病的诊断和病理的深入研究，同时推动生物学、医学以及生物信息学等多种学科的研究和发展。
传统的聚类方法虽然成熟，但各有优缺点。例如基于划分的聚类简单高效，易于实现，但要求事先确定聚类的数目，这直接影响预测结果，因为蛋白质相互作用网络中聚类数目实际是不知道的。基于层次化聚类能够挖掘任意形状的模块，并且能够使整个网络呈现出清晰的层次结构，但对噪声非常敏感。基于密度的局部搜索算法能够识别相对稠密子图，与蛋白质模块内部联系紧密的特性相符合，且允许模块重叠，但却无法挖掘蛋白质相互作用网络中的那些非稠密的子图。
近些年来许多研究者提出了各种群智能优化算法，并将它们应用到不同的领域，但它们也有自身的局限性。而布谷鸟搜索算法不仅具有简单、参数少、易于实现等优点，同时因其两个非常关键的组件Levy flights随机游动和偏好随机游动而具有显著的高效性。为此本文将布谷鸟搜索算法应用到蛋白质相互作用网络中，并对聚类结果的评价方法进行了研究。
首先将布谷鸟搜索算法应用到蛋白质相互作用网络中。借鉴常用的蛋白质相似度函数提出了一种新的相似度衡量函数，介绍了基本的布谷鸟算法，详细描述该算法应用到PPI网络中的实验步骤，PPI数据上的实验表明该算法可以有效地对蛋白质相互作用网络进行聚类，而且聚类结果的正确率和f-measure优于人工鱼群与功能流算法。
然后，对蛋白质相互作用网络聚类评价方法进行研究。介绍并分析了四种有代表性的蛋白质相互作用聚类评价方法，即p-value、匹配统计量、基于准确率和查全率的综合评价以及基于层结构的hF-measure，在此基础上考虑了主错误划分类与该预测类的相似性，提出了新的罚分函数和新的Sf-measure评价方法。仿真结果表明各评价方法的特点及Sf-measure评价误方法的有效性及合理性。