PPI网络的改进谱聚类算法

蛋白质相互作用(PPI)网络是生物信息学的一个新的研究领域。近年来谱聚类算法在未知蛋白质的功能预测方面发挥了重要作用,但是它要求事先确定聚类数目,为此提出了一种基于边的得分搜索的谱聚类算法。该算法采用谱聚类方法对数据进行预处理,并通过构造蛋白质节点之间的边的得分矩阵找到数据样本之间的相关性,同时融入粒子群算法来确定边的得分的最佳选择阈值,最后用广度优先遍历结点的方法得到聚类结果。算法在PPI网络数据集上进行了测试,结果表明该算法不但可以自动确定聚类数目,而且聚类结果的正确率和F-measure值都得到了提高。     

基于蜂群和广度优先遍历的PPI网络聚类

蛋白质交互作用(PPI)网络聚类算法是研究和揭示蛋白质功能的主要方法之一。由于PPI网络的特性,传统算法不能有效聚类。文中提出一种基于蜂群和广度优先遍历的聚类算法。为避免噪声点对实验结果的干扰,在预处理阶段利用距离-密度算法确定聚类个数,剔除噪声点。然后利用结点网络综合特征值确定初始聚类中心,利用广度优先遍历搜索算法进行聚类。再采用改进的蜂群算法自动寻找最优合并阈值。最后用正确率和查全率对该算法进行性能评价并对算法中一些重要参数进行仿真分析,仿真结果表明该聚类算法有效提高PPI网络的聚类效果。     

基于模糊谱聚类的不确定蛋白质相互作用网络功能模块挖掘

针对谱聚类融合模糊C-means（FCM）聚类的蛋白质相互作用（PPI）网络功能模块挖掘方法准确率不高、执行效率较低和易受假阳性影响的问题，提出一种基于模糊谱聚类的不确定PPI网络功能模块挖掘（FSC-FM）方法。首先，构建一个不确定PPI网络模型，使用边聚集系数给每一条蛋白质交互作用赋予一个存在概率测度，克服假阳性对实验结果的影响；第二，利用基于边聚集系数流行距离（FEC）策略改进谱聚类中的相似度计算，解决谱聚类算法对尺度参数敏感的问题，进而利用谱聚类算法对不确定PPI网络数据进行预处理，降低数据的维数，提高聚类的准确率；第三，设计基于密度的概率中心选取策略（DPCS）解决模糊C-means算法对初始聚类中心和聚类数目敏感的问题，并对预处理后的PPI数据进行FCM聚类，提高聚类的执行效率以及灵敏度；最后，采用改进的边期望稠密度（EED）对挖掘出的蛋白质功能模块进行过滤。在酵母菌DIP数据集上运行各个算法可知，FSC-FM与基于不确定图模型的检测蛋白质复合物（DCU）算法相比，F-measure值提高了27.92%，执行效率提高了27.92%；与在动态蛋白质相互作用网络中识别复合物的方法（CDUN）、演化算法（EA）、医学基因或蛋白质预测算法（MGPPA）相比也有更高的F-measure值和执行效率。实验结果表明，在不确定PPI网络中，FSC-FM适合用于功能模块的挖掘。     

融合人工鱼群机理的PPI网络聚类模型与算法

预测蛋白质交互作用(Protein-Protein Interaction,PPI)网络中未知蛋白质的功能,是生物信息学的一个研究热点.目前基于功能流的方法能有效地解决PPI网络的聚类问题,但是其正确率偏低、时间复杂度较高.为此提出了一种融合人工鱼群机理的PPI网络聚类模型与算法:将人工鱼看作一组聚类中心,觅食行为是指从每个聚类中心开始向它的邻接结点搜索并添加结点到该聚类模块中;接下来将目标函数值最大的人工鱼对应的一组聚类模块看作初始的聚类结果,对应鱼群的追尾行为;剩下的人工鱼开始执行聚群行为,判断对应的聚类模块与初始的聚类结果之间的相似度.如果相似度低于给定的阈值,则将聚类模块添加到初始的聚类结果中.PPI数据集上的仿真实验表明,该算法可以自动确定聚类数目,而且聚类结果的正确率和算法的运行效率都优于功能流算法.     

基于XGBoost与拓扑结构信息的蛋白质复合物识别算法

蛋白质相互作用(PPI)网络中存在大量不确定性及已知蛋白质复合物数据的不完整性,单独地根据结构信息进行搜索或对已知复合物进行监督学习的方法在识别蛋白质复合物的准确性上存在不足。对此,提出一种XGBoost模型与复合物拓扑结构信息相结合的搜索方法(XGBP)。首先,根据复合物拓扑结构信息进行特征提取;然后,把所提取的特征用XGBoost模型进行训练;最后,将拓扑结构信息与监督学习方法相结合,建立特征与复合物之间的映射关系以提高蛋白质复合物预测的准确性。该算法分别与目前流行的马尔可夫聚类算法(MCL)、极大团聚类方法(CMC)、基于核心-附属结构算法(COACH)、快速层级聚类算法(HC-PIN)、基于重叠邻居的扩展聚类(ClusterONE)、分子复合物检测算法(MCODE)、基于不确定图模型的蛋白质复合物检测方法(DCU)和加权核心-附属算法(WCOACH)这八种非监督学习算法和三种监督学习方法贝叶斯网络(BN)、支持向量机(SVM)、回归模型(RM)进行比较,所提方法在精准度、敏感度、F-measure方面显示出良好的性能。     

蛋白质相互作用网络分析的图聚类方法研究进展

随着可获得的大规模蛋白质相互作用数据的迅速增长,从系统水平上对细胞机制的基本组件和结构的理解成为了一种可能。如今所面临的最大挑战是如何通过分析此类复杂的相互作用数据来反映细胞组织、进程以及功能的规律。基于图理论的聚类方法是分析蛋白质相互作用数据的有效手段。本文将从蛋白质相互作用网络(PPI网络)的图模型、聚类算法、评估方法及应用几个方面描述PPI网络聚类分析的最新研究进展。最后,讨论该方向研究所面临的挑战及进一步的研究方向。     

PPI网络聚类的评价方法的研究与应用

蛋白质相互作用网络(Protein-Protein Interaction,PPI)聚类结果的评价方法的研究是检测PPI网络功能模块聚类结果正确与否的关键。介绍并分析了4种有代表性的PPI网络聚类的评价方法,即p-value、匹配统计量、基于准确率和查全率的综合评价以及基于层结构的hF-measure,在此基础上考虑了主错误划分类与该预测类的相似性,提出了新的罚分函数和新的Sf-measure评价方法。仿真结果表明了各评价方法的特点及Sf-measure评价方法的有效性及合理性。     

基于人工免疫系统的蛋白质相互作用网络聚类算法

提出了一种基于人工免疫特性的蛋白质相互作用(PPI)网络聚类模型与算法以期提高其辨识准确率。在该算法中将聚类中心作为抗原,将邻接的节点作为抗体,通过计算抗体与抗原之间的亲和度,将其作为记忆细胞把节点划分到聚类中;然后选择优秀抗体作为疫苗,尝试将疫苗注入聚类模块并进行更新,通过与注射前的模块适应度进行比较,不断更新记忆细胞。对PPI数据集上的数据进行了仿真,实验结果表明,与功能流算法(FLOW)相比,所提方法的正确率和查全率的几何平均值均得到了提高。     

基于蚁群聚类的动态加权PPI网络复合物挖掘

针对基于蚁群聚类的蛋白质复合物挖掘算法中,静态PPI网络难以真实反映细胞的动态特性,收敛速度较慢、聚类准确性和召回率不高等问题,提出一种基于模糊粒度和紧密度的蚁群聚类动态加权PPI网络复合物挖掘方法（FGCDACC-DPC）。首先基于动态PPI网络的拓扑特性和生物特性设计了综合性权值度量（comprehensive weight metric,CWM）,准确描述了蛋白质之间的相互作用;其次根据复合物的基本特征,构建一组稠密且高度共表达的复合核,然后设计模糊粒度和紧密度的拾起放下模型对其余节点聚类,降低了计算复杂度和随机性,加快聚类速度;最后基于功能信息传递和时序功能相关的思想分别构建了局部和全局权值更新策略,实现不同代蚁群和不同时刻网络之间的功能信息传递,提高聚类准确性。将FGCDACC-DPC算法应用在DIP数据上进行复合物挖掘,实验结果表明该算法的精度和召回率较高,能够较准确地识别蛋白质复合物。     

蛋白质功能模块检测的聚类方法综述

在蛋白质相互作用（Protein-Protein Interaction，PPI）网络中检测蛋白质功能模块有助于预测未知蛋白质的功能模块。随着蛋白质相互作用有效数据迅速增长，如何通过PPI网络获得有效的蛋白质功能模块成为最大挑战。阐述PPI网络的发展及现状，通过对当前蛋白质功能模块检测算法进行归纳总结，把它们分为单元聚类和多元聚类，并对每类的代表性方法进行详细阐述；讨论蛋白质相互作用网络功能模块检测研究所面临的挑战及未来研究方向。     

一种基于云模型改进蚁群聚类算法的研究

基于云模型在非规范知识的定性、定量表示及其相互转换过程中的优良特征结合LF蚁群聚类算法的基本思想,提出了一种基于云模型的蚁群聚类算法。从模仿蚂蚁堆积的尸体的基本模型出发,引入了相似因子和相异因子的概念,通过在邻域内进行快速云模型动态概念软划分产生最大的内聚核,进而重新定义接受分数的计算公式,能够使聚类收敛速度更快、聚类结果更纯,更符合人的常理判断。实验结果表明新算法对聚类质量有很好的效果。     

改进的自适应谱聚类NJW算法

聚类算法是近年来国际上机器学习领域的一个新的研究热点。为了能在任意形状的样本空间上聚类,学者们提出了谱聚类和图论聚类等优秀的算法。首先介绍了图论聚类算法中的谱聚类经典NJW算法和NeiMu图论聚类算法的基本思路,提出了改进的自适应谱聚类NJW算法。提出的自适应NJW算法的优点在于无需调试参数,即可自动求出聚类个数,克服了经典NJW算法需要事先设置聚类个数且需反复调试参数δ才能得出数据分类结果的缺点。在UCI标准数据集及实测数据集上对自适应NJW算法与经典NJW算法、自适应NJW算法与NeiMu图论聚类算法进行了比较。实验结果表明,自适应NJW算法方便快捷,且具有较好的实用性。     

蛋白质相互作用网络的蜂群信息流聚类模型与算法

蛋白质相互作用网络的聚类算法研究是充分理解分子的结构、功能及识别蛋白质的功能模块的重要方法.很多传统聚类算法对于蛋白质相互作用网络聚类效果不佳.功能流模拟算法是一种新型聚类算法,但该算法没有考虑到距离的作用效果并且需要人为地设置合并阈值,带有主观性.文中提出了一种新颖的基于蜂群优化机理的信息流聚类模型与算法.该方法中,数据预处理采用结点网络综合特征值的排序来初始化聚类中心,将蜂群算法的蜜源位置对应于其聚类中心,蜜源的收益度大小对应于模块间的相似度,采蜜蜂结点的所有邻接点按照结点网络综合特征值的降序排列,作为侦察蜂的搜索邻域.采用正确率、查全率等指标对聚类效果做出客观评价,并对算法的一些关键参数进行仿真、对比与分析.结果表明新算法不仅克服了原功能流模拟算法的缺点,且其正确率和查全率的几何平均值最高,能够有效地识别蛋白质功能模块.     

一种基于蚁群聚类的快速算法

从模仿蚂蚁堆积的尸体的基本模型出发，引入了相似因子和相异因子的概念，通过重新定义接受分数的计算公式，能够使聚类结果更纯，聚类速度更快。实验结果表明新算法明显改善了聚类质量。     

大规模生物网络马尔可夫聚类的并行化算法

马尔可夫聚类算法（MCL）是在大规模生物网络中寻找模块的一个有效方法，能够挖掘网络结构和功能影响力较大的模块。算法涉及到大规模矩阵计算，因此复杂度可达立方阶次。针对复杂度高的问题，提出了基于消息传递接口（MPI）的并行化马尔可夫聚类算法以提高算法的计算性能。首先，生物网络转化成邻接矩阵；然后，根据算法的特性，按照矩阵的规模判断并重新生成新矩阵以处理非平方倍数矩阵的计算；其次，并行计算通过按块分配的方式能够有效地实现任意规模矩阵的运算；最后，循环并行计算直至收敛，得到网络聚类结果。通过模拟网络和真实生物网络数据集的实验结果表明，与全块集体式通信（FCC）并行方法相比，平均并行效率提升了10个百分点以上，因此可以将该优化算法应用在不同类型的大规模生物网络中。