论文部分内容阅读
蛋白质相互作用(Protein-Protein Interaction, PPI)网络是生命活动中一种极其重要的生物分子关系网络,利用计算方法从PPI网络中检测功能模块是目前生物信息学中一项重要的研究课题。根据PPI网络的拓扑结构和功能模块的特点,研究人员已经提出了多种不同类型的检测方法。其中,基于群集智能的聚类方法是近年来新出现的一种模块检测方法,已经成为PPI网络功能模块检测的一个研究热点。蚁群优化(Ant Colony Optimization, ACO)是一种典型的群集智能算法,基于蚁群优化的思想,本文针对PPI网络功能模块检测问题,开展了以下两个方面的研究工作:(1)针对PPI网络噪声较高,检测到模块精度不高的问题,通过融合蛋白质的功能注释信息,提出了基于蚁群寻优机制的功能模块检测算法。算法首先根据PPI网络的拓扑结构和蛋白质的基因本体(Gene Ontology, GO)信息,分别计算蛋白质节点间的拓扑距离和功能相似性距离,并将其结合到新的启发函数中。然后,利用新的启发函数引导蚁群进行路径寻优,以发现能够反映拓扑特征和功能信息的最优路径。最后,根据设定的阈值断开最优路径得到初始的功能模块,并利用结合功能注释的合并策略对初始模块进行合并,以提高检测模块的质量。在四个通用PPI数据集上与其他一些经典检测算法的实验相比,新算法在多项评价指标上表现出了卓越的性能。(2)针对上一工作中算法存在容易陷入局部最优的缺点,提出了蚁群优化与多Agent进化相结合的功能模块检测算法。算法在每一次迭代中首先采用蚁群优化进行路径寻优。然后,通过多Agent的三种进化操作,对得到的寻优路径做进一步优化。之后,在Agent的编码路径上进行信息素更新,引导蚂蚁在接下来的搜索中跳出局部最优。最后,当算法迭代结束时,根据Agent的自动解码机制得到初始的功能模块,并通过合并策略得到最终的模块。多组实验结果表明,新算法能有效克服局部最优的缺点,与其他一些算法相比具有明显的竞争力。论文实现了两种新颖的PPI网络功能模块检测方法,不仅扩展了蚁群优化的应用领域,也为其他复杂网络的研究工作提供了有益的借鉴。