一种新的图划分算法在PPI网络模块化中的研究

王晓芳，贾宗维

（1．晋中师范高等专科学校，山西 晋中030600；2．山西农业大学 信息科学与工程学院，山西 太谷030801）

随着高通量生物蛋白质交互作用网络信息数据的不断扩大，越来越多的研究人员投身到预测蛋白质相互作用和蛋白质功能这一新兴的研究领域。众多研究表明，细胞中的蛋白质并不是孤立行动，而是通过彼此间的相互作用来实现特定的生物功能。蛋白质间的相互作用不仅关系到生物体的新陈代谢同时也是探究许多疾病病因的关键所在。因此，对蛋白质交互网络的研究对于蛋白质未知功能的预测以及了解细胞机制的结构有着十分重要的科学研究意义［1］。从高通量的生物蛋白质交互网络中通过聚类研究提取功能模块，有助于了解蛋白质相互作用机理和对未知蛋白质功能的预测。

近年来，酵母双杂交技术［2］、质谱分析技术［3］、蛋白质芯片技术［4］的发展和应用，使得高速增长的蛋白质相互作用数据可用于进一步分析研究。研究人员提出了许多蛋白质相互作用网络的聚类算法，用以分析蛋白质功能模块和预测未知蛋白质功能。它们大致分为基于层次聚类的方法、基于图划分和基于密度的局部搜索的聚类方法，如maximal clique方法［5］、RNSC方法［6］、MCODE方法［7］。本文在深入分析蛋白质网络的拓扑属性和蛋白质节点间的相互关系后，提出了一种基于蛋白质节点相似性的度量准则，以最优化模块度为目标函数的图聚类算法，用来发现蛋白质交互网络中的功能模块，实验结果表明所探测的功能模块内部的确是密集连接的。……