一种基于同配性的重叠蛋白质复合体检测算法

蛋白质复合体在生物过程中具有重要的作用,从蛋白质互作用网络中进行蛋白质复合体检测是后基因时代的一项具有挑战性的任务。种子扩展方法是一种从蛋白质互作用网络中进行重叠蛋白质复合体检测的有效技术。然而,现有方法面临两方面的问题:1)在选择种子结点时通常仅仅考虑了网络中结点的直接邻居之间的连接紧密度,难以充分体现结点在局部邻域子图内的重要性;2)在簇的扩展过程中假设候选结点之间是相互独立的,忽略了候选结点的添加顺序可能对聚类结果带来的影响。为了解决以上问题,文中基于生物网络同配性提出了一种重叠蛋白质复合体检测算法。该算法利用结点的二阶邻域信息来度量结点的重要性,进而选择种子结点,在簇扩展过程中利用同配性实现多个候选结点的批量添加。为了对重叠聚类结果进行评价,提出了一种重叠复合体评价指标F-overlap。与其他复合体检测算法在蛋白质互作用数据集上的对比实验结果表明,所提算法能够有效地进行重叠蛋白质复合体检测。     

一种蛋白质复合体模块度函数及其识别算法

蛋白质复合体对于研究细胞活动具有重要意义.随着新的生物实验技术的不断出现,产生了大量的蛋白质相互作用网络.通过对蛋白质相互作用网络进行聚类识别蛋白质复合体是当前研究热点.然而,目前大多数蛋白质复合体识别算法的性能不够理想.为此,提出了蛋白质复合体模块度函数(PQ),并在此基础上提出了基于蛋白质复合体模块度函数的模块合并(based on protein complexes modularity function for merging modules,BMM)算法.BMM算法首先识别网络中一些稠密子图作为初始模块,然后依据PQ函数对这些初始模块进行合并,最终得到了质量较高的蛋白质复合体.将识别出的复合体分别与2种已知的蛋白质复合体数据集进行比对,结果表明BMM算法具有很好的识别性能.此外,与其他最新的识别算法相比,BMM算法的识别准确率较高.     

基于多维聚类挖掘的异常检测方法研究

网络异常检测是网络管理中非常重要的课题,因此已在近年来得到广泛研究.人们在该领域提出了许多先进的网络流量异常检测方法,但是自动准确地对网络流量进行分类和识别来发现网络中的异常流量仍然是一个非常具有挑战性的问题.文中提出了一种基于多维聚类挖掘的异常检测方法,通过两个阶段来实现异常检测.第一阶段先通过多维聚类挖掘算法,自动对网络中的流量进行多维聚类,第二阶段通过计算多维聚类的异常度来实现异常检测.通过文中的方法,网络中的异常流量被自动归类到不同的有意义的聚类中,通过对这些聚类进行分析可以发现网络中的异常行为.最后通过实验对算法进行了验证,结果表明该方法能够有效检测网络中的异常流量.     

面向Web社会网络搜索的人名同一性判断

随着人们在互联网上的行为日益丰富,互联网上的社交行为和关系逐渐接近传统的客观世界的社交网络,并能够真实反映出人与人之间在客观世界的真实关系。可以从互联网中通过搜索的方式来构建一个真实客观世界的社会网络。社会网络搜索技术及其方法逐渐成为目前的研究热点,如何对每个Web进行人名同一性判断是社会网络搜索的关键技术。为了从文本中抽取准确的特征并降低向量维度,本文给出了一个基于C-value和逆文档频率IDF的特征向量权值计算方法;实现了基于余弦夹角的相似度计算的算法;通过对文本聚类算法中层次聚类算法和划分聚类算法的研究,给出一种改进的层次聚类算法来实现人名同一性判断。以搜索引擎的人名检索结果进行测试,说明了基于改进的层次聚类算法能有效地提高人名同一性判断的性能。     

基于模块度优化的蛋白质网络集团探测与分析

探测蛋白质相互作用网络中的功能模块对于理解生物系统的组织和功能具有重要的意义。目前,普遍的做法是将蛋白质相互作用网络表示成一个图,利用各种图聚类算法来挖掘功能模块。本文采用了基于模块度优化的图聚类算法来探测蛋白质相互作用网络中的集团,从具有2617个节点11855个相互作用的酵母蛋白相互作用网络中探测出68个集团。对于得到的集团,首先从拓扑结构的角度验证其的确是内部连接稠密的子图,然后分析了MIPS数据库中ComplexCat提供的已知的蛋白质复合体与这些集团的重叠情况,发现很多蛋白质复合体完全包含在某些集团中,最后使用超几何聚集分布的P值来分析一个集团对某个特定功能的富集程度,并根据最小的P值对应的功能来注释该集团的主要功能,发现集团中大部分的蛋白质具有相同的功能。研究结果表明,该方法探测的集团具有重要的生物学功能意义。     

蛋白质网络中复合体和功能模块预测算法研究

预测蛋白质相互作用网络中的复合体和功能模块对于理解生物系统的组织和功能具有重要的意义.到目前为止,已经出现了大量的蛋白质复合体和功能模块预测算法及相关的软件,这些算法各具特色,但同时也具有一定的局限.文中对典型的聚类预测算法进行了研究,依据算法特性对它们进行了分类,并从算法思想、关键技术以及算法性能等方面进行了分析和比...     

一种基于增量式谱聚类的动态社区自适应发现算法

针对当前复杂网络动态社区发现的热点问题, 提出一种面向静态网络社区发现的链接相关线性谱聚类算法, 并在此基础上提出一种基于增量式谱聚类的动态社区自适应发现算法. 动态社区发现算法引入归一化图形拉普拉斯矩阵呈现复杂网络节点之间的关 系,采用拉普拉斯本征映射将节点投影到k维欧式空间.为解决离群节点影响谱聚类的效果和启发式确定复杂网络社区数量的问题, 利用提出的链接相关线性谱聚类算法发现初始时间片的社区结构, 使发现社区的过程能够以较低的时间开销自适应地挖掘复杂网络社区结构. 此后, 对于后续相邻的时间片, 提出的增量式谱聚类算法以前一时间片聚类获得的社区特征为基础, 通过调整链接相关线性谱聚类算法实现对后一时间片的增量聚类, 以达到自适应地发现复杂网络动态社区的目的. 在多个数据集的实验表明, 提出的链接相关线性谱聚类算法能够有效地检测出复杂网络中的社区结构以及基于 增量式谱聚类的动态社区自适应发现算法能够有效地挖掘网络中动态社区的演化过程.     

基于层次聚类的离群点分析方法

发现离群点并合理地解释离群点对数据挖掘结果的运用有重要意义,通过对离群点属性的检测可以发现其离群特性,进而更加准确地解释聚类结果。针对在聚类结果中出现的不同离群点及其特性,提出将层次聚类算法应用于离群点分析,通过元胞自动机距离变换算法实现凝固层次聚类,实现了簇间距离的度量;定义了演化周期上的平均度量距离,能够发现不同聚类层次上的离群点及其离群特性。该算法能够在得到聚类结果的同时,有效地解释离群点的属性,并具有较低的计算复杂度和并行计算以及向高维空间扩展的特性。通过试验数据进行了实证研究,验证了算法的有效性。     

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

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

基于中心度的标签传播时间序列聚类方法

为了实现时间序列自动聚类,以及更为细致地描述时间序列之间的结构关系,引入社区发现方法来研究时间序列聚类.针对标签传播方法在标签传播过程中具有较强不确定性,以及算法对网络结构较为敏感等问题,提出一种基于中心度的标签传播时间序列聚类方法;通过构建时间序列网络空间结构,将每条时间序列看作一个节点,根据每个节点的中心度来得到标签更新顺序;计算节点对于每个簇的归属度,再利用节点的归属度和标签的传播实现节点的划分,从而实现时间序列聚类.所提方法通过分析时间序列之间的连接关系来发现其在欧氏空间的结构特征,进而实现空间结构的有效划分.实验结果表明,所提方法无需确定初始簇中心,能够有效划分人工数据网络和真实社会网络,在时间序列数据聚类中取得了良好的聚类效果.     

Social Network Clustering and Visualization using Hierarchical Edge Bundles

The hierarchical edge bundle (HEB) method generates useful visualizations of dense graphs, such as social networks, but requires a predefined clustering hierarchy, and does not easily benefit from existing straight‐line visualization improvements. This paper proposes a new clustering approach that extracts the community structure of a network and organizes it into a hierarchy that is flatter than existing community‐based clustering approaches and maps better to HEB visualization. Our method not only discovers communities and generates clusters with better modularization qualities, but also creates a balanced hierarchy that allows HEB visualization of unstructured social networks without predefined hierarchies. Results on several data sets demonstrate that this approach clarifies real‐world communication, collaboration and competition network structure and reveals information missed in previous visualizations. We further implemented our techniques into a social network visualization application on facebook.com and let users explore the visualization and community clustering of their own social networks.     

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

针对谱聚类融合模糊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网络聚类

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

PPI网络的改进谱聚类算法

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

基于复合物参与度和密度的关键蛋白质预测

针对在蛋白质相互作用网络上的关键蛋白质识别只关注拓扑特性,蛋白质相互作用数据中存在较高比例的假阳性数据以及基于复合物信息的关键蛋白质识别算法对节点的邻域信息和复合物的挖掘对关键蛋白质的识别影响效果考虑不够全面等导致的识别准确率和特异性不高的问题,提出一种基于复合物参与度和密度的关键蛋白质预测算法PEC。首先融合GO注释信息和边聚集系数构造加权PPI网络,克服假阳性对实验结果的影响;基于蛋白质相互作用的边权重,构造相似度矩阵,设计特征值间的最大本征差值来自动确定划分数目K,同时根据加权网络中的蛋白质节点度来选取K个初始聚类中心,进而利用谱聚类结合模糊C-means聚类算法实现复合物的挖掘,提高聚类的准确率,降低数据的维数;其次基于蛋白质节点的复合物参与度以及节点邻域子图密度,设计出关键节点的关键性得分。在DIP和Krogan 2个数据集上,将PEC与DC、BC、CC、SC、IC、PeC、WDC、LIDC、LBCC和UC 10种经典算法相比,实验结果表明,PEC算法能够识别出更多的关键蛋白质,且聚类结果的准确率和特异性较高。     

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

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

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

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

针对蛋白质复合体检测的自学习图聚类

蛋白质复合体是由两条或多条相关联的多肽链组成, 在生物过程中起着重要作用. 假如用图表示蛋白质–蛋白质相互作用(protein-protein interactions, PPI)网络数据, 那么从中找出紧密耦合的蛋白质复合体是非常困难的, 特别是在近年来PPI网络的容量大大增加的情况下. 在本文中, 通过对称非负矩阵分解, 针对蛋白质复合体检测问题提出了一种图聚类方法, 该方法可以有效地从复杂网络中检测密集的连通子图. 并且将此方法和当前最先进的一些方法在3个PPI数据集中用同一个基准进行比较. 实验结果表明, 本文的方法在3个拥有不同大小和密度的数据集中均显著优于其它方法.     

基于SOM聚类的垃圾处理方式可视化分析方法

针对全国各省份垃圾处理方式的数据,提出一种混合可视分析方法。为了从多角度分析数据,混合U矩阵、平行坐标以及Small-Multiple 3种可视化技术,设计并实现了3种可视化视图的交互联动。首先,对数据进行聚类处理,将各省份近年的垃圾处理方式划分类别,采用SOM神经网络聚类算法实现聚类。然后,针对SOM聚类结果,采用U矩阵的方式进行可视化,并采用平行坐标描述每个聚类结果的各个属性。为了分析数据的地理属性及时序属性,采用Small-Multiple可视化技术。最后,实现多视图联动、刷新技术等交互方式,帮助用户自行探索数据,实现多视图的交互展示与分析。实验表明,这种混合可视方式可达到较好的多属性交互可视化效果,能够帮助用户了解并分析我国垃圾处理方式的分布及趋势。