随着人类基因组计划的实施,生物医学进入后基因时代,系统全面地理解蛋白质之间通过相互作用完成各项生命活动的规律已成为研究的热点之一。蛋白质互作用网络作为复杂网络之一,有明显的社区结构,这些社区结构通常对应于特定的功能模块,称为蛋白质复合物。从大规模蛋白质互作用网络中识别蛋白质复合物对预测蛋白质功能,解释特定的生物进程具有重要作用。基于图聚类算法,发现蛋白质互作用网络中的社区结构(也称为簇),是进行蛋白质复合物识别的有效方法。基于种子扩展策略的图聚类算法可以有效发现大多数已知的蛋白质复合物,然而这类算法的聚类结果受种子节点选取的影响较大,且扩展过程一旦结束,聚类结果将不再调整。本文从智能优化算法角度设计图聚类算法发现蛋白质互作用网络中的稠密社区,进而进行蛋白质复合物识别,主要包括以下两方面工作:(1)提出了基于遗传策略的图聚类算法GAGC(Genetic Algorithm based Graph Clustering,GAGC),设计了遗传算法的染色体表示方式;改进IPCA的种子节点选择方式,产生初始种群;选择f-measure作为种群进化的目标函数,评价染色体质量;设计了染色体对齐方式,以进行交叉操作;通过染色体交叉和变异,对聚类结果进行优化。通过与DPClus、MCODE、IPCA、ClusterOne、HC-PIN、CFinder经典算法进行了对比,实验表明,算法能够提高解的多样性,进而扩大图聚类算法的搜索空间,提高了蛋白质复合物识别算法的性能。(2)提出了基于离散粒子群优化的图聚类算法DPSOPC(Discrete Particle Swarm Optimization for Protein Complexes,DPSOPC),首先对粒子位置、速度、目标函数,粒子状态更新规则等进行定义;在粒子状态更新过程中,调整簇的结构,优化聚类结果;输出粒子群的全局最优解作为最终复合物发现结果。在5个真实的酿酒酵母互作用网络上与DPSOPC、MCODE、IPCA、ClusterOne等算法进行了对比实验,实验结果表明,算法能够实现较高的recall值。