论文部分内容阅读
蛋白质相互作用(Protein-Protein Interaction,简称为PPI)网络是由生物体内的蛋白质和蛋白质之间的相互作用组成,属于复杂网络,它具有小世界性、无标度分布和功能模块化的特点。PPI网络功能模块的检测是后基因时代生物信息学研究的前沿课题之一,得到了国内外学者们的广泛关注和深入研究。PPI网络功能模块检测不仅对理解生物系统的组织和功能具有重要意义,而且是生物行为理解、蛋白质功能预测和药物设计的基础。与此同时,群集智能方法由于具有强大的全局寻优能力,故在许多复杂问题求解中获得了广泛的应用。近年来,基于群集智能的PPI网络功能模块检测算法已经陆续涌现,成为该领域中的一个新的研究热点。本文对基于蚁群聚类机制的PPI网络功能模块检测进行了较为深入地研究,主要工作包括:(1)为了提高功能模块检测质量,对蚁群聚类模型和信息传递机制进行研究,提出新的PPI网络功能模块检测算法。该算法首先利用网络节点的聚类系数,获得种子节点集合;其次,利用基于概率模型的拾起操作和放下操作,对PPI网络中的节点进行聚类;再次,利用每代蚂蚁最优的聚类结果和节点间功能相似性评分,对相似性函数进行更新,实现不同代蚂蚁间的信息传递机制;最后,利用后处理过程,修正初始聚类结果,提高聚类效果。与其他检测算法的实验比较表明,该算法不仅可以有效地检测PPI网络中的功能模块,而且在不同的PPI数据库上具有良好的性能。(2)为了克服基于蚁群聚类机制的检测算法在求解大规模PPI网络时在时间性能上的不足,结合图聚类中多级算法的思想,提出了具有多级框架的蚁群聚类检测算法。该算法首先利用新的匹配策略对大规模的PPI网络进行粗粒度化,以降低待聚类网络规模,得到较小规模的PPI网络;其次,利用上一个工作提出的基于蚁群聚类的检测算法对得到的网络进行聚类;最后,通过消粒度得到原始网络的聚类结果,并利用精炼过程避免聚类结果陷入局部最优。在一些大规模数据集上的实验表明,该算法的检测速度比上一个工作有较大地提高;而与其他检测算法相比,该算法也能得到较好的聚类结果。本文通过对基于蚁群聚类机制的PPI网络功能模块检测算法的研究,一方面丰富了PPI网络功能模块检测算法的理论研究,另一方面也提高了基于蚁群聚类机制的检测算法在大规模PPI网络上的求解能力。