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

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

NOBEL: 一种基于拓扑信息与监督学习的蛋白质复合物识别方法

蛋白质复合物对于生物学家有效了解细胞组织和功能具有重要意义,如何通过计算方法从蛋白质-蛋白质相互作用(PPI)网络中识别复合物是当前研究热点之一。然而,由于PPI网络中存在大量假阴性和假阳性噪声数据且现有已知蛋白质复合物并不完整,使得如何克服PPI网络的噪声问题,以及更好地利用已知蛋白质复合物,成为蛋白质复合物识别亟待解决的关键问题。为此,该文提出一种基于蛋白质复合物拓扑信息,利用监督学习进行蛋白质复合物识别的算法(NOBEL)。首先,NOBEL根据蛋白质的生物信息和拓扑信息构建加权PPI网络,降低了网络中的噪声问题;然后,通过加权PPI网络和未加权PPI网络提取复合物拓扑信息作为特征,并根据提取的特征训练监督学习模型,使得监督学习模型能有效学习复合物蕴含的信息;最后,将训练好的模型应用于PPI网络识别蛋白质复合物。作者在四种真实PPI网络上进行了实验,实验结果表明,NOBEL与其他七种蛋白质复合物识别算法相比,在F-measure方面分别至少提高了4.39%(Gavin)、1.32%(DIP)、2.39%(WI-PHI_core)和2.34%(WI-PHI_extend)。     

基于遗传算法的蛋白质复合物识别算法

蛋白质互作用网络是一种典型的复杂网络,呈现了明显的社区结构。网络中的社区对应于功能模块,通常被看作蛋白质复合物。蛋白质复合物识别对预测蛋白质功能,解释特定生物进程具有重要作用。基于种子节点扩展的图聚类方法在蛋白质复合物识别中应用广泛。针对此类算法最终结果受种子节点的影响较大,并且在簇的形成过程中搜索空间有限等问题,提出了一种基于遗传算法的蛋白质复合物识别算法GAGC(genetic algorithm based graph clustering),其中个体表示聚类结果(类别之间可能存在重叠节点),以F-measure值作为种群进化的目标函数。算法采用IPCA(improvement development clustering algorithm)算法产生初始种群;针对初始种群,设计了染色体对齐方式以进行交叉操作产生下一代种群。通过与DPClus、MCODE、IPCA、Cluster One、HC-PIN、CFinder等经典算法的对比实验表明,GAGC算法能够扩大图聚类算法的搜索空间,提高解的多样性,进而提高蛋白质复合物检测的性能。     

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

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

采用隐马尔科夫模型的蛋白质复合物识别研究

动态蛋白质网络的构建和复合物识别问题是生物信息学领域目前研究的热点.针对现有的算法在解决前述问题上的不足,提出了一种基于隐马尔科夫模型的蛋白质复合物识别算法(HMM-PC).首先基于蛋白质的基因共表达特性构建初始蛋白质网络,然后利用蛋白质的共享功能注释、共享结构域和连接强度等信息来对网络进行加权,得到动态蛋白质网络.在此基础上,考虑前一时刻蛋白质网络拓扑结构信息对当前时刻蛋白质网络拓扑结构信息的影响,采用隐马尔科夫模型描述蛋白质复合物与网络个体间的相互关系,进而将动态蛋白质网络中的复合物识别问题建模为隐马尔科夫模型中的最优状态序列发现问题,并采用维特比算法识别得到蛋白质复合物.最后通过理论分析证明了所提算法的复杂度较低.采用DIP数据集和MIPS数据集中的酵母蛋白质网络作为测试对象,大量的仿真实验结果也表明,HMM-PC算法的鲁棒性较强,在查全率、查准率、F-measure和效率等方面的性能都要优于现有的复合物识别算法.     

基于加权网络和局部适应度的蛋白质复合物识别算法

蛋白质复合物识别对分析蛋白质网络的结构特征和模块功能具有重要意义。通常在蛋白质网络中挖掘稠密子图或模块来识别其中的蛋白质复合物,限制了其应用范围和识别的准确性。针对该问题,提出了一种基于加权网络和局部适应度的蛋白质复合物识别算法,该算法综合稠密子图的密度指标和模块性定义了新的局部适应度函数,并基于边聚集系数构建加权的蛋白质网络,根据权值选择边,在加权蛋白质网络中将种子边不断聚类扩展,从而获取具有最大综合适应度的子图作为蛋白质复合物。在酵母蛋白质等多个实际网络中试验表明,该算法能够有效提升蛋白质复合物识别的准确性。     

基于图卷积的蛋白质复合物筛选模型

蛋白质复合物的预测对生物研究至关重要,现有的预测算法主要是基于蛋白质相互作用网络的局部结构发现算法,其存在一定的局限性,无法利用已知复合物作为先验知识,无法有效融合蛋白质生物关联性数据,因此其预测结果中会存在部分不符合复合物形成规律的样本。本文提出基于图卷积的复合物筛选模型,该模型充分考虑了蛋白质特征,在蛋白质复合物对应的局部图中将特征进行深度融合,从而有效地对蛋白质复合物进行评分,识别并剔除一般复合物预测算法结果中的低分复合物样本,提高其预测的准确性。     

一种新的基于多数据源的蛋白质复合物识别算法

蛋白质复合物是许多生物过程得以实现的基石。蛋白质相互作用数据中的假阳性和假阴性对各种识别蛋白质复合物的计算方法有不良影响。为了解决这一问题,1种新的蛋白质复合物识别算法(ICMDS,Identifying Complexes based on Multiple Data Sources)被提出。该方法整合基因表达谱、关键蛋白质信息和蛋白质相互作用3种生物数据进行蛋白质复合物的挖掘。首先,ICMDS重新定义了2个相互作用的蛋白质之间的功能相似性(FS,Functional Similarity)。然后,ICMDS选择已知的关键蛋白质作为种子构建蛋白质复合物。为了消除冗余的复合物,ICMDS算法也设计了冗余过滤子程序。另外,ICMDS也使用非关键蛋白质作为种子并将之扩展为蛋白质复合物。实验结果表明ICMDS识别蛋白质复合物的能力明显优于其他计算方法。     

模拟鸽子优化过程的蛋白质复合物识别算法

蛋白质复合物的检测对人类了解细胞组织和疾病预测起着至关重要的作用。然而,当前的蛋白质复合物识别方法的准确率低,对噪音敏感等缺点导致其识别效果并不理想。提出了一种新的蛋白质复合物识别方法PIOC(pigeon-inspired optimization clustering)。该方法根据蛋白质复合物的特性提出了簇的紧密邻接点概念和附件对核心的附着度概念,基于这两个概念,PIOC通过模拟鸽子优化算法中鸽子寻找目的地的过程来识别蛋白质复合物;结合鸽子算法中先全局搜索再局部搜索的特性和蛋白质复合物的核心附件结构,先通过鸽子算法中地图罗盘操作的全局搜索形成蛋白质复合物的核心,再通过鸽子算法地标操作的局部搜索将附件蛋白质聚集到核心簇中形成蛋白质复合物。基于酵母蛋白质相互作用网络DIP上的实验表明,PIOC比当前其他的蛋白质复合物识别算法能更有效地识别蛋白质复合物。     

基于加权子网参与度和多源信息融合的关键蛋白质识别算法

现有关键蛋白质识别算法对生物信息考虑不全面、识别准确率亦有待提高,针对此问题,提出一种高效关键蛋白质识别算法PDWS。首先,结合由亚细胞定位信息获取到的蛋白质位置和蛋白质相互作用网络边聚类系数构建加权网络;其次,依据蛋白质所处亚细胞位置,提出亚细胞定位区室子网参与度指标;最后,融合亚细胞定位区室子网参与度和蛋白质复合物子网参与度指标,多维度度量蛋白质关键性。在DIP和Krogan两个标准数据集上的实验结果表明,PDWS算法性能优于PeC、PCSD等已有算法,可识别出更多特定结构的关键蛋白质,且识别精度分别达到0.76与0.73。     

基于邻居信息聚合的子图同构匹配算法

图匹配在现实中被广泛运用,而子图同构匹配是其中的研究热点,具有重要的科学意义与实践价值。现有子图同构匹配算法大多基于邻居关系来构建约束条件,而忽略了节点的局部邻域信息。对此,提出了一种基于邻居信息聚合的子图同构匹配算法。首先,将图的属性和结构导入到改进的图卷积神经网络中进行特征向量的表示学习,从而得到聚合后的节点局部邻域信息;然后,根据图的标签、度等特征对匹配顺序进行优化,以提高算法的效率;最后,将得到的特征向量和优化的匹配顺序与搜索算法相结合,建立子图同构的约束满足问题（CSP）模型,并结合CSP回溯算法对模型进行求解。实验结果表明,与经典的树搜索算法和约束求解算法相比,该算法可以有效地提高子图同构的求解效率。     

Towards generalization of semi-supervised place classification over generalized Voronoi graph

With the progress of human–robot interaction (HRI), the ability of a robot to perform high-level tasks in complex environments is fast becoming an essential requirement. To this end, it is desirable for a robot to understand the environment at both geometric and semantic levels. Therefore in recent years, research towards place classification has been gaining in popularity. After the era of heuristic and rule-based approaches, supervised learning algorithms have been extensively used for this purpose, showing satisfactory performance levels. However, most of those approaches have only been trained and tested in the same environments and thus impede a generalized solution. In this paper, we have proposed a semi-supervised place classification over a generalized Voronoi graph (SPCoGVG) which is a semi-supervised learning framework comprised of three techniques: support vector machine (SVM), conditional random field (CRF) and generalized Voronoi graph (GVG), in order to improve the generalizability. The inherent problem of training CRF with partially labeled data has been solved using a novel parameter estimation algorithm. The effectiveness of the proposed algorithm is validated through extensive analysis of data collected in international university environments.     

Clustering support vector machines for protein local structure prediction

Understanding the sequence-to-structure relationship is a central task in bioinformatics research. Adequate knowledge about this relationship can potentially improve accuracy for local protein structure prediction. One of approaches for protein local structure prediction uses the conventional clustering algorithms to capture the sequence-to-structure relationship. The cluster membership function defined by conventional clustering algorithms may not reveal the complex nonlinear relationship adequately. Compared with the conventional clustering algorithms, Support Vector Machine (SVM) can capture the nonlinear sequence-to-structure relationship by mapping the input space into another higher dimensional feature space. However, SVM is not favorable for huge datasets including millions of samples. Therefore, we propose a novel computational model called Clustering Support Vector Machines (CSVMs). Taking advantage of both theory of granular computing and advanced statistical learning methodology, CSVMs are built specifically for each information granule partitioned intelligently by the clustering algorithm. This feature makes learning tasks for each CSVM more specific and simpler. CSVMs modeled for each granule can be easily parallelized so that CSVMs can be used to handle complex classification problems for huge datasets. Average accuracy for CSVMs is over 80%, which indicates that the generalization power for CSVMs is strong enough to recognize the complicated pattern of sequence-to-structure relationships. Compared with the conventional clustering algorithm, our experimental results show that accuracy for local structure prediction has been improved noticeably when CSVMs are applied.     

GSO:基于图神经网络的深度学习计算图子图替换优化框架

深度学习在各种实际应用中取得了巨大成功,如何有效提高各种复杂的深度学习模型在硬件设备上的执行效率是该领域重要的研究内容之一.深度学习框架通常将深度学习模型表达为由基础算子构成的计算图,为了提高计算图的执行效率,传统的深度学习系统通常基于一些专家设计的子图替换规则,采用启发式搜索算法来优化计算图.它们的不足主要有:1)搜...     

Alleviating the computational load of the probabilistic algorithms for circles detection using the connectivity represented by graph

The probabilistic algorithms are effective and widely used to recognize the curves in machine vision and image processing. In this paper, a novel algorithm for detecting circles is presented. It is based on the observation that the connectivity can help to alleviate the computational load of the probabilistic algorithm. A graph model is introduced to express connectivity in the detected edges, and a modified depth-first-search algorithm is developed to segment the whole graph into connected subgraphs and then partition the complex subgraph into simple paths. Then, four pixels are randomly selected from the sampling set, consisting of one proper path or several consecutive paths, to detect circles. The connectivity constraint is further employed to verify the candidates of circles to eliminate the pseudo ones. The experiments, comparing the proposed algorithm with the randomized Hough transform and the efficient randomized circle detection algorithm, show that it has the advantages of computational efficiency and robustness.     

Handling continuous attributes in an evolutionary inductive learner

This work analyzes experimentally discretization algorithms for handling continuous attributes in evolutionary learning. We consider a learning system that induces a set of rules in a fragment of first-order logic (evolutionary inductive logic programming), and introduce a method where a given discretization algorithm is used to generate initial inequalities, which describe subranges of attributes' values. Mutation operators exploiting information on the class label of the examples (supervised discretization) are used during the learning process for refining inequalities. The evolutionary learning system is used as a platform for testing experimentally four algorithms: two variants of the proposed method, a popular supervised discretization algorithm applied prior to induction, and a discretization method which does not use information on the class labels of the examples (unsupervised discretization). Results of experiments conducted on artificial and real life datasets suggest that the proposed method provides an effective and robust technique for handling continuous attributes by means of inequalities.     

基于两阶段学习的半监督支持向量机分类算法

提出了一种基于两阶段学习的半监督支持向量机(semi-supervised SVM)分类算法.首先使用基于图的标签传递算法给未标识样本赋予初始伪标识,并利用k近邻图将可能的噪声样本点识别出来并剔除;然后将去噪处理后的样本集视为已标识样本集输入到支持向量机(SVM)中,使得SVM在训练时能兼顾整个样本集的信息,从而提高SVM的分类准确率.实验结果证明,同其它半监督学习算法相比较,本文算法在标识的训练样本较少的情况下,分类性能有所提高且具有较高的可靠性.     

A framework combines supervised learning and dense subgraphs discovery to predict protein complexes

Rapidly identifying protein complexes is significant to elucidate the mechanisms of macromolecular interactions and to further investigate the overlapping clinical manifestations of diseases.To date,existing computational methods majorly focus on developing unsupervised graph clustering algorithms,sometimes in combination with prior biological insights,to detect protein complexes from protein-protein interaction(PPI)networks.However,the outputs of these methods are potentially structural or functional modules within PPI networks.These modules do not necessarily correspond to the actual protein complexes that are formed via spatiotemporal aggregation of subunits.In this study,we propose a computational framework that combines supervised learning and dense subgraphs discovery to predict protein complexes.The proposed framework consists of two steps.The first step reconstructs genome-scale protein co-complex networks via training a supervised learning model of l2-regularized logistic regression on experimentally derived co-complexed protein pairs;and the second step infers hierarchical and balanced clusters as complexes from the co-complex networks via effective but computationally intensive k-clique graph clustering method or efficient maximum modularity clustering(MMC)algorithm.Empirical studies of cross validation and independent test show that both steps achieve encouraging performance.The proposed framework is fundamentally novel and excels over existing methods in that the complexes inferred from protein co-complex networks are more biologically relevant than those inferred from PPI networks,providing a new avenue for identifying novel protein complexes.