蛋白质贝尔金路由器设置

SCIENTIASINICAInformationis中国科学:信息科学2017年第47卷第10期:1349–1368c2017《中国科学》杂志社www.
scichina.
cominfocn.
scichina.
com论文基于降维的蛋白质不相关功能预测余国先1*,傅广垣1,王峻1,郭茂祖21.
西南大学计算机与信息科学学院,重庆4007152.
北京建筑大学电气与信息工程学院,北京100044*通信作者.
E-mail:gxyu@swu.
edu.
cn收稿日期:2017–01–10;接受日期:2017–03–16;网络出版日期:2017–08–31国家自然科学基金(批准号:61402378,61571163,61532014,61671189)、重庆市研究生科研创新项目(批准号:CYS16070)、重庆市基础与前沿研究计划项目(批准号:cstc2014jcyjA40031,cstc2016jcyjA0351)和中央高校基本科研业务费(批准号:2362015X-K07,XDJK2016B009,XDJK2017D061)资助项目摘要蛋白质是生命活动的重要物质基础,对其功能的准确标注可以极大地促进生命科学的研究与发展.
已有的蛋白质功能预测方法通常仅关注利用蛋白质具有某些功能的信息(正样例),并没有关注利用蛋白质不相关的功能信息(负样例).
已有研究表明,结合蛋白质负样例可以降低蛋白质功能预测的复杂度并提高预测精度.
本文提出一种基于降维的蛋白质不相关功能预测方法(predictingirrelevantfunctionsofproteinsbasedondimensionalityreduction,IFDR).
IFDR通过在蛋白质互作网邻接矩阵和蛋白质–功能标记关联矩阵上分别进行随机游走,挖掘蛋白质之间的内在关系和预估蛋白质的缺失功能标记,再分别利用奇异值分解将上述2个矩阵投影降维为低维实数矩阵,最后利用半监督回归预测负样例.
在酵母菌、人类和拟南芥的蛋白质数据集上的实验表明,IFDR比已有相关算法能够更准确地预测负样例,对互作网络和功能标记空间的降维均可以提高负样例预测精度.
关键词蛋白质功能预测,正负样例,蛋白质互作网,功能标记,降维1引言蛋白质是最主要的生命活动载体和功能执行者,对蛋白质功能的准确标注可以帮助人类更好的理解生命机理,在药物研发、疾病分析等方面都有着很多应用.
随着高通量测序技术和分析技术的广泛应用,收集获取的基因/蛋白质序列和网络数据日益增多,基于生物湿实验测定蛋白质功能的方法通量低、成本高,难以满足对海量蛋白质数据进行快速功能标注的要求.
如何有效地利用海量数据进行蛋白质功能预测是后基因组时代生物信息学的核心问题之一[13].
计算学方法能够利用各种生物数据并融合生物学规律实现大规模蛋白质功能预测,为后续湿实验提供较高置信度的蛋白质功能信息,减少实验规模,节约实验成本和时间.
蛋白质功能标注数据库[4]中约95%的蛋白质功能信息由计算学引用格式:余国先,傅广垣,王峻,等.
基于降维的蛋白质不相关功能预测.
中国科学:信息科学,2017,47:1349–1368,doi:10.
1360/N112017-00009YuGX,FuGY,WangJ,etal.
Predictingirrelevantfunctionsofproteinsbasedondimensionalityreduction(inChinese).
SciSinInform,2017,47:1349–1368,doi:10.
1360/N112017-00009余国先等:基于降维的蛋白质不相关功能预测方法获得[5].
研究发现蛋白质的氨基酸序列决定其结构,进而决定其生物功能,因此很多方法基于氨基酸序列和结构预测蛋白质功能[6,7].
蛋白质之间通过互作完成具体的生物功能,互作的蛋白质通常共享一些相同的功能,构成蛋白质互作网,因而大量基于互作网的分类方法被应用到功能预测中[810].
单种蛋白质数据(如氨基酸序列和蛋白质互作网)描述蛋白质功能特性的能力有限,一些学者尝试整合多种异构生物数据更全面地描述蛋白质,提出多种基于数据融合的蛋白质功能预测方法[1114].
基因本体(geneontology,GO)[4]是一种广泛使用的基因及其产物(包括蛋白质和RNA)的功能标记范式,GO利用有向无环图描述功能标记间层次结构关系,图中每个节点描述并对应一种功能标记,节点间有向边描述功能之间的关系(isapartof和regulate),子节点是父节点功能的进一步细化.
GO中存在称为TruePathRule的规则:当一个蛋白质标注某个节点对应的功能时,它也标注该节点的所有祖先节点对应的功能;而当明确蛋白质不具有该节点对应的功能时,它也不具有该节点的所有子节点对应的功能[4,15].
一个蛋白质通常参与到不同的生命过程中,发挥多个不同的生物学功能,可标注多个功能标记,因此蛋白质可以看作多标记样本[1618].
早期的蛋白质功能预测方法[9,10]通常把功能预测问题转化为二分类问题,单独对每个功能标记进行预测分析,这类方法忽略了标记之间的关联性,取得的精度有限.
一些学者将功能预测问题转化为多标记分类问题进行研究[1619],通过利用标记间的关系提高了功能预测的精度.
然而这些方法仅利用了标记间的水平关系,并未考虑标记间层次结构关系[20].
近期一些学者结合标记间层次结构关系进行功能预测提高了预测精度[12,15,2022].
虽然多标记学习方法已被广泛用于蛋白质功能预测,精度也在不断地提升,但其中的假阴性问题仍未很好地解决,原因是蛋白质功能标注数据库通常仅登记蛋白质具有某个功能的信息(正样例),极少登记与该蛋白质不相关的功能信息(亦即蛋白质功能的负样例).
为保持与正样例的对称和便于行文,下文简称蛋白质的不相关功能为蛋白质负样例.
数据库中并未登记的蛋白质与标记的关联性并不代表该标记为蛋白质的负样例,仅表明该标记与蛋白质是否正关联尚需生物实验验证或目前缺乏相关证据[5,23,24].
由于已知的蛋白质功能信息并不完整,这种未登记的关联性占据非常大的比例,而现有很多蛋白质功能预测算法均把这些未登记的关联性假定为负样例[17,18,25],损失了预测精度.
从GO的TruePathRule可知,若已知某个标记为蛋白质的负样例,则该标记节点的所有子孙节点对应的标记也为该蛋白质的负样例.
研究发现,通过蛋白质已知的功能信息,预先选出一部分负样例,可以显著地缩小功能预测问题的规模,提高预测精度[24,26,27].
Mostafavi等[11]利用一种启发式方法选择负样例,若存在兄弟关系的成对标记中仅已知一个标记为某个蛋白质正样例,则另一个标记选为该蛋白质的负样例.
由于蛋白质的已知功能信息很不完善且受生物学家研究兴趣的影响[5,23],这种启发式方法通常容易错误地选择负样例[26].
Youngs等[24]提出一种参数化Bayes方法(ALBNeg)计算成对标记间的经验条件概率,再结合每个蛋白质已标注的功能标记和上述条件概率预估其他标记也标注到该蛋白质的概率,选择概率值最小的标记为该蛋白质的负样例.
ALBNeg在计算标记间条件概率时仅考虑了数据库中登记的正样例,并没有考虑标记间的结构关系,计算的条件概率存在偏差.
为此,Youngs等[26]通过GO上的TruePathRule规则将一个蛋白质已标注的标记节点的祖先节点对应的标记也标注到该蛋白质,再重新计算标记间经验条件概率,提出一种负样例预测方法SNOB,SNOB利用与ALBNeg类似的方法预测负样例.
此外,他们将每个蛋白质视为一个文档,蛋白质已标注的标记为该文档的单词,再利用LantentDirichletAllocation[28]预测负样例.
上述方法预估的标记间条件概率完全依赖于不完整的蛋白质功能信息.
针对上述不足,Fu等[29]提出NegGOA方法综合利用标记间的层次结构相似度和经验条件概率,再结合蛋白质已知的功能标记在基因本体所在的有向无环图上进行重启动随机游走[30]预测蛋白质的负样例.
实验表明NegGOA选取的负样例的假阴性数更少,1350中国科学:信息科学第47卷第10期选择的负样例显著地提升了功能预测精度.
上述方法仅关注对标记结构和已有正样例的利用,忽略了对已有少量负样例和蛋白质其他特征信息的利用.
傅广垣等[31]提出一种基于正负样例的蛋白质功能预测方法(ProPN),该方法通过符号混合图描述蛋白质与标记的正关联(正样例)和负关联(负样例)、蛋白质互作和标记间关联关系,再通过混合图上的符号标记传播预测蛋白质负样例.
蛋白质互作网中存在一定量的假阳性互作,这些假阳性互作会引起正负样例的过度传播.
此外,大部分功能标记是非常稀疏的,它们标注的蛋白质个数非常少,在标记传播中这些稀疏标记容易被其他标记覆盖,也会降低负样例预测的准确性.
在分析上述研究工作的基础上,本文借助成分扩散分析[3234]和奇异值分解(singlevaluede-composition,SVD)[35]提出一种基于网络和标记空间降维的蛋白质不相关功能预测方法(predictingirrelevantfunctionsofproteinsusingdimensionalityreduction,IFDR).
IFDR首先在蛋白质互作网对应的邻接矩阵上进行重启动随机游走挖掘蛋白质潜在的互作关系,再利用SVD获得互作网的低维实数特征向量矩阵,矩阵中每行刻画对应蛋白质在互作网中的主要拓扑结构信息.
同时,IFDR基于蛋白质已知的功能和基因本体结构利用重启动随机游走预估蛋白质的缺失正样例,再利用SVD将蛋白质–功能标记关联矩阵投影转化为一个低维关联矩阵.
最后在降维后的蛋白质互作网和蛋白质–功能标记关联矩阵上利用半监督回归预测蛋白质负样例.
在酵母菌、人类和拟南芥3个模式生物上的负样例预测实验表明,IFDR能够较已有相关方法更准确预测负样例,通过SVD对互作网和标记空间进行降维可以挖掘并利用蛋白质互作关系和标记间关联关系,提升负样例预测精度.
2基于网络和标记空间降维的蛋白质功能负样例预测IFDR主要由蛋白质互作网上的成分扩散分析及基于SVD的降维压缩表示,蛋白质–功能标记关联矩阵中的缺失正样例预估及基于SVD的降维压缩表示,基于压缩的蛋白质特征向量数据和蛋白质–功能标记向量数据的半监督线性回归3部分构成,下文分别对上述内容进行详细分析介绍.
2.
1蛋白质互作网的降维表示高通量技术的广泛应用产生了海量的多源异构蛋白质数据,蛋白质互作网是其中一种最常见和常用的蛋白质数据集,互作网中每个节点对应一个蛋白质,节点间的边描述蛋白质之间的互作信息.
互作网可以描述蛋白质如何通过互作来完成特定生物功能和参与到具体的生命过程中,这些互作的蛋白质更有可能具有相同的功能.
很多学者对蛋白质互作网的生物学特性进行建模分析,设计方法预测蛋白质功能[810,22,31,32,36].
然而高通量技术收集的蛋白质网络数据包含的互作信息并不全面,还存在一定的噪声互作,这些假阳性互作和缺失的(假阴性)互作会降低功能预测的精度.
近期Cao等[32]利用成分扩散分析刻画互作网中每个蛋白质细粒度拓扑结构并加以利用,提升了预测精度.
但这类方法依然受假阳性和假阴性互作的影响.
为此,Cho等[33]和Wang等[34]将降维与成分扩散分析进行结合,首先在蛋白质互作网的邻接矩阵上进行基于重启动随机游走的成分扩散分析并更新邻接矩阵,获得每个蛋白质节点的分布信息及其与其他蛋白质的关联信息,再利用一种基于Kullback[37]的Logistic回归模型对邻接矩阵进行降维,获得每个蛋白质的低维特征向量,通过低维特征向量刻画该蛋白质与其他蛋白质之间的拓扑结构.
实验表明,与在原始互作网上进行基于成分扩散分析的功能预测方法相比,结合降维可以进一步提高预测精度.
为了克服假阳性和假阴性互作对蛋白质负样例预测的影响,受上述工作启发,IFDR在蛋白质互1351余国先等:基于降维的蛋白质不相关功能预测作网的邻接矩阵上进行成分扩散分析,再利用SVD将更新的邻接矩阵通过降维转化为低维向量形式.
令GP∈Rn*n为由n个蛋白质构成的互作网对应邻接矩阵,当蛋白质i与j存在相互作用时,则GP(i,j)存在一条权重不为0的边,其边权重表示这两个蛋白质互作的强度或置信度.
为方便计算,本文对GP进行了归一化处理以保证一个蛋白质与其他蛋白质互作的强度之和为1,具体归一化方式如下:GPP=D1PGP,(1)DP是一个对角矩阵,DP(i,i)=∑nj=1GP(i,j).
令S0P=GPP,StP∈Rn*n表示第t步重启动随机游走后蛋白质互作网的扩散矩阵:St+1P(i,v)=(1γ)n∑j=1GPP(i,j)StP(j,v)+γGPP(i,v),(2)其中γ∈(0,1)控制随机游走的重启动概率,它调节随机游走对互作网全局和局部拓扑结构的影响,γ越大表示局部结构权重越大.
由于0GPP(i,j)1,式(2)必收敛.
令SP表示重启动随机游走达到收敛时的平稳分布,亦即最终的扩散状态.
互作网中两个蛋白质拥有相似的扩散状态,意味着它们在互作网中相对其他节点有相似的位置,表明它们的功能很可能相似[32].
但由于探知的蛋白质互作信息受限于高通量实验技术和生命分子活动的随机性[3],上述方法获得的最终扩散状态仍在一定程度上受噪声互作的影响.
此外,若将SP的每行当作一个蛋白质的特征向量,再在其上训练分类器预测蛋白质功能,则会面临高维数据上的巨大计算开销和维数灾难问题.
为克服上述问题,IFDR在SP上应用SVD将它降维压缩为实数向量特征矩阵,具体方式如下:SP=UPΛPVTP,(3)其中UP∈Rn*n和VP∈Rn*n也称为SP的左右特征向量矩阵,ΛP∈Rn*n为对角奇异值矩阵,对角线中的每个元素均不小于0.
UP中的每列由SPSPT的特征向量构成,VP中的每列由SPTSP的特征向量构成,由于SP为对称矩阵,因此UP=VP.
IFDR选取UP中前d个列向量构成矩阵UdP∈Rn*d和ΛP中前d(dn)个最大对角元素构成对角矩阵ΛdP∈Rd*d实现对SP的低维向量表示.
令XP=[x1,xn]∈Rn*d为n个蛋白质对应的低维向量特征矩阵,XP的计算方式如下:XP=UdP(ΛdP)12.
(4)通过将高维SP压缩为XP不仅避免了维数灾难问题,也能在保持网络扩散模式的同时降低假阳性和假阴性互作的影响,后续实验分析也将证明基于SVD对蛋白质互作网进行降维可提高负样例的预测精度.
2.
2蛋白质–功能标记关联矩阵的降维表示蛋白质的功能标记非常不平衡[15],大量稀疏标记标注的蛋白质个数非常少,只有少量标记标注的蛋白质个数较多.
例如在蛋白质功能标注数据库中(截止2016–08–31),已知人类的约20000个蛋白质与24429个功能标记存在关联,而这些标记中只有9216个标注的蛋白质数量大于3,有5976个标记标注的蛋白质数量超过10,仅有1513个标记标注的蛋白质数量大于100,其他(约62%)的标记标注的蛋白质数量均小于3.
这些稀疏标记的正样例非常少以致训练的分类器精度不高,容易出现过1352中国科学:信息科学第47卷第10期拟合问题.
Yu等[20]观察发现蛋白质新增的功能标记通常对应该蛋白质已有功能标记节点的子孙节点,这些子孙节点对应的标记标注的蛋白质个数通常小于其祖先节点.
在负样例预测中,若仅基于功能标记的频率信息预测负样例,则很容易误判稀疏标记为蛋白质的负样例[29].
从GO结构和其上的TruePathRule规则可知,这些稀疏标记通常描述了更详细的生物学功能.
Pandey等[38]发现利用标记间的关联关系可以提升功能预测算法在稀疏标记上的精度.
基于多标记学习的蛋白质功能预测方法通过不同的策略利用标记间的关联关系也提升了精度[17,20,25,27,39].
然而上述这些方法并没有充分考虑标记不平衡特性.
针对这一问题,Wang等[34]提出clusDCA方法.
clusDCA在GO有向无环图对应的邻接矩阵上进行成分扩算分析,利用SVD对邻接矩阵进行降维压缩,再将蛋白质–功能标记关联矩阵GF∈Rn*m(m为标记个数)投影到低维空间YcF∈Rn*c(cm),最终通过优化一个矩阵R∈Rd*n(XPRYcF)预测n蛋白质与c个压缩的标记之间的关联性.
然而clusDCA并没有考虑蛋白质功能信息的不完整性和蛋白质新增功能标记的模式规律.
与clusDCA相比,IFDR不对GO对应的邻接矩阵进行类似蛋白质互作网的成分扩散分析和降维.
IFDR结合标记间的层次结构关系和蛋白质已有的功能信息,在GO的有向无环图上进行有向的重启动随机游走,对蛋白质的缺失正样例进行建模,进而减少误判稀疏功能标记为蛋白质负样例的风险,再利用SVD对噪声特征鲁棒的特点对蛋白质–功能标记关联矩阵GF进行降维压缩表示,降低错误预估正样例的破坏作用.
蛋白质–功能标记关联矩阵GF通过如下方式进行初始化:当标记s为蛋白质i的正样例时GF(i,s)=1;当标记s为蛋白质i的负样例时GF(i,s)=1;当它们之间的正负关联性未知时GF(i,s)=0.
Yu等[20]统计发现,对于蛋白质的缺失正样例,来自直接父节点标记预估的置信度远大于其他祖先节点标记.
这是因为当已知该蛋白质标注了父节点标记时,由TruePathRule可知该蛋白质也标注它的其他祖先节点标记,反之则不一定成立.
基于上述发现,本文初始仅考虑具有直接父子关系的标记节点间的信息传递,并通过以下方式设置标记间的转移概率:p(v|s)=nv/ns,nv>0,1/|ch(s)|,nv=0,(5)其中ns和nv为分别标注s和v的蛋白质数量,ch(s)为s的直系孩子节点集合,v∈ch(s),|ch(s)|为该集合的大小.
由TruePathRule可知nsnv.
当nv=0时,仅表明n个蛋白质中目前还没有蛋白质标注功能v,原因可能是缺少相关的实验验证,针对这种情况,本文设定s向v的转移概率为s的孩子节点数的倒数.
为使s向其所有孩子节点转移概率总和为1,对转移概率进行如下归一化:p(v|s)=p(v|s)∑u∈ch(s)p(u|s).
(6)类似地,对GF进行如下归一化:GFF=D1FGF,(7)其中DF∈Rn*n是一个对角矩阵DF(i,i)=∑ms=1|GF(i,s)|,取GF(i,s)的绝对值是因为GF中存在正负样例.
在上述设置的基础上,IFDR结合蛋白质已知的功能信息在有向无环图上进行重启动随机游走预估蛋白质的缺失正样例(GF(i,v)=0),具体预估方式如下:St+1F(i,v)=(1γ)n∑s∈par(v)St+1F(i,s)p(v|s)+γGFF(i,v),(8)1353余国先等:基于降维的蛋白质不相关功能预测其中par(v)为v的父母节点集合,StF(i,v)为第t次随机游走时预估的i与v的关联大小,S0F=GFF.
由于γ∈(0,1),p(v|s)1,StF(i,v)StF(i,s),亦即蛋白质i与s(父节点标记)的关联大小总是不小于与v(子节点标记)的关联大小.
这种预估方法较好地利用了蛋白质新增正样例的模式,但容易引入较多的假阳性预估.
为了降低假阳性预估的影响,IFDR利用SVD对噪声特征鲁棒的优点,将SF(式(8)收敛时n个蛋白质与m个标记的关联大小矩阵)分解为SF=UFΛFVTF,(9)其中UF∈Rn*n,VF∈Rm*m,ΛF∈Rn*m为对角奇异值矩阵.
一种常用的去噪方式是取UF的前c列构成矩阵UcF∈Rn*c,ΛF的前c(cm)个最大奇异值构成对角矩阵ΛcF∈Rc*c和VF的前c列构成矩阵VcF∈Rm*c,通过UcFΛcFVcF近似重构矩阵SF.
在此基础上,再利用XP和去噪后的SF进行蛋白质功能预测.
然而这种方法涉及的标记集合依然非常大,甚至出现蛋白质数量小于标记数量的情况,训练的分类器面临过拟合的风险.
针对上述问题,IFDR利用UcF和ΛcF将SF投影到低维空间YcF=[y1,y2,yn](YcF∈Rn*c),方式如下:YcF=UcF(ΛcF)12,(10)IFDR再基于XP和YcF进行蛋白质功能预测.
假定YcF∈Rn*c为IFDR预测的n个蛋白质与压缩的c个功能的关联性矩阵,IFDR通过YcFPmF(PmF∈Rc*m)将YcF映射回原始的m个功能标记空间,PmF的定义如下:PmF=(ΛcF)12VcF.
(11)YcF中的每行可以看作对应蛋白质压缩的c维标记向量,PmF中每列可以看作是原始标记的c维实数特征表示,该列编码存储了对应标记与其他标记的关系[35,40].
通过对SF的压缩表示,蛋白质的正负样例在c维标记空间可向它们相似的标记传递.
2.
3蛋白质负样例预测IFDR基于蛋白质互作网GP的压缩向量矩阵XP和蛋白质–功能标记关联矩阵GF的压缩向量矩阵YcF训练分类器进行负样例预测.
不同于一般的0-1(或1,1)形式的标记指示矩阵,YcF为实数向量矩阵,且其中包含值为负的元素.
为此,本文采用半监督线性回归[41]预测蛋白质负样例.
基础线性方程如下:f(x)=WTx+b,(12)其中W∈Rd*c为投影预测向量,b∈Rc*1为偏移向量,f(x)∈Rc为x在c个压缩的功能标记上的输出,或x与c个标记的关联性大小.
类似流形正则化半监督分类框架[42],本文的半监督线性回归目标方程形式如下:J(W,b)=argminW,bn∑i=1Ψ(xi,yi,f(xi))+α∥f∥2I+β∥f∥2H,(13)其中Ψ(xi,yi,f(xi))为预先定义的损失函数,∥f∥2I为基于n个蛋白质之间的特征相似度定义的平滑损失项,∥f∥2H为控制f(x)复杂度避免其过度拟合的正则项.
在本文中,Ψ(xi,yi,f(xi))选用平方误差1354中国科学:信息科学第47卷第10期损失函数:Ψ(xi,yi,f(xi))=∥f(xi)yi∥22=tr((WTxi+byi)(WTxi+byi)T),(14)其中tr()为求矩阵的迹.
∥f∥2I的定义与计算方式如下:∥f∥2I=12n∑i,j=1∥f(xi)f(xj)∥22Sij=12n∑i,j=1WTxiWTxj22Sij=trWTn∑i=1(xiSiixTi)WWTn∑i,j=1(xiSijxTj)W=tr(WTXTP(DS)XPW)=tr(WTXTPLXPW),(15)其中Sij为蛋白质xi与xj之间的相似度,本文采用余弦相似性度量计算蛋白质之间的相似度.
D为对角矩阵,Dii=∑Nj=1Sij,L=DS为图Laplace矩阵,它对称半正定.
最小化∥f∥2I的目的是使具有相似特征表示的蛋白质标注相似的功能标记集合,因为这些特征相似的蛋白质在互作网中有相似的成分扩散模式,通常构成一个功能模块,协作完成生物学功能[36,43].
控制分类器复杂度的正则项∥f∥2H定义如下:∥f∥2H=tr(WTW).
(16)在上述定义的基础上,J(W,b)可以表示为J(W,b)=tr((WTXTP+b1TnYcFT)(WTXTP+b1TnYcFT)T+αWTXTPLXPW+βWTW),(17)其中1n∈Rn*1为元素值全为1的列向量.
分别对J(W,b)求W与b的导数,并令导数为0,可得W=(XTPUXP+αXTPLXP+βId)1XTPUYcF,(18)b=1n(YcFWTXP)T1n,(19)其中Id为d*d的单位矩阵,U=In1/n,In为n维单位矩阵.
令YcF=[f(x1),f(x2)f(xn)],IFDR通过PmF将YcF映射回原始标记空间:YmF=YcFPmF,(20)YmF∈Rn*m存储IFDR预测的n个蛋白质与m个功能的关联度大小.
YmF(i,v)值越大表明v为蛋白质i的正样例的可能性越高,值越小表明v为该蛋白质负样例的概率越高.
3实验3.
1数据集本文从BioGrid数据库[44](日期:2016–08–01)中分别下载3个典型模式物种(人类(H.
sapiens),酵母菌(S.
cerevisiae),拟南芥(A.
thaliana))的蛋白质互作网数据,同时还下载了对应的GO数据库和蛋白质–功能标记关联数据,并对互作网中的蛋白质进行功能标注.
GO描述了功能标记之间的层次1355余国先等:基于降维的蛋白质不相关功能预测表1实验数据集统计信息,Avg±Std对应每个蛋白质的平均功能标记个数和对应的方差Table1Datasetstatistics,Avg±StdistheaveragenumberofannotationsperproteinandstandarddeviationProteins(n)BranchFunctions(m)Positives(Negatives)Avg±StdBP15373790787(16324)49.
17±63.
14H.
sapiens16082CC2931307635(26963)19.
13±34.
49MF5990158369(12042)9.
84±18.
55BP5256222754(1374)37.
02±31.
65S.
cerevisiae6017CC2566120392(5456)20.
00±23.
85MF250147558(799)7.
90±6.
89BP5948229193(3132)24.
67±28.
01A.
thaliana9289CC2397179944(45523)19.
37±31.
44MF255367695(1846)7.
29±9.
29结构关系,这些标记分布在3个不相交的分支上,分别是生物过程(biologicalprocess,BP)、分子功能(molecularfunction,MF)和细胞组分(cellularcomponent,CC).
与以往实验类似,本文剔除GO中'obsolete'的功能标记;为避免循环预测,还剔除了证据属性为IEA(inferredfromelectronicannotation)的标注信息.
考虑到数据库仅登记蛋白质的直接功能标记,这些标记过于稀疏,本文利用GO上的TruePathRule对蛋白质功能信息进行增补,将蛋白质正样例对应标记节点的祖先节点标记也标注到相应的蛋白质上,蛋白质负样例对应标记节点的子孙节点也标注为相应蛋白质的负样例.
表1列出了上述3个物种的蛋白质已有标记统计信息,可以看到GO数据库已经开始登记少量的蛋白质负样例,但相对正样例来说其数量仍然很少.
最后一列Avg±Std对应每个蛋白质的平均功能标记个数和对应的方差,较大的方差说明蛋白质的功能信息并不完整,一些蛋白质的功能信息较完备,另一些蛋白质的功能信息存在较多缺失,还有一部分蛋白质的功能信息完全未知.
3.
2对比方法与评价度量本文将通过负样例预测的假阴性个数和预测的负样例对蛋白质功能预测精度的提升情况综合检验负样例预测的有效性.
在负样例预测实验中,本文以当前最新的NegGOA[29],ProPN[31],SNOB[26]和基准方法Random作为IFDR的对比方法.
为分析IFDR中缺失标记预估和半监督线性回归的影响,本文引入clusDCA[34]和IFDR-DCA作为对比方法.
NegGOA,ProPN,SNOB和clusDCA在引言或2.
2小节中做了详细介绍,不做赘述.
IFDR-DCA是IFDR的变种,它在蛋白质互作网和GO上分别进行成分扩散分析和SVD,再将蛋白质–功能标记关联矩阵映射到低维空间,然后利用IFDR的半监督线性回归目标方程预测负样例.
基准方法Random从所有未标注到某个蛋白质的标记集合中随机选择标记为该蛋白质负样例,为了减少随机偏差,本文随机运行基准方法100次,取100次运行结果的均值作为其负样例预测的最终结果.
所有对比方法的参数设置都按照原始论文提供的参数或方法进行设置.
如NegGOA中,α=β=0.
5,迭代次数为4;ProPN中α=0.
1,β=0.
9;clusDCA中bp=0.
8,对GO降维的目标维度为2500.
IFDR中蛋白质互作网空间投影维度d和标记空间投影维度c统一设置为300,下文实验将对这2个参数的敏感性进行分析.
在负样例预测实验中,本文选用假阴性预测数(falsenegatives,FNs)[26,29]为评测指标,它统计预测结果为负样例但真实结果为正样例的错误情况.
本文下载了上述3个物种蛋白质早期的功能标注数据(归档日期分别为2015–07–01和2014–06–01),并用3.
1小节中同样方法和流程对蛋白质互作网中1356中国科学:信息科学第47卷第10期的蛋白质进行功能标注.
所有方法均基于2015年的蛋白质功能标注数据进行蛋白质负样例预测,再利用2016年更新的蛋白质功能标注数据检验负样例的预测质量,若一个预测的负样例在更新的蛋白质功能标注数据中为正样例,则产生了一个FN.
本文另外选用4个常用的评价度量MarcroF1,RAccuracy,AUC和Fmax评估蛋白质功能预测的质量.
MarcroF1是一种以标记为中心的评价度量,它先求取每个标记的F1-score,再取这些标记F1-score的均值,这一评价度量受稀疏功能标记影响较大.
RAccuracy从全局上检验n个蛋白质中有多少缺失正样例被准确预测.
AUC首先对每个标记分别计算ROC(receiveroperatingcharacteristic)曲线下的面积,再取m个标记对应面积的均值.
与AUC一样,Fmax是国际大规模蛋白质功能预测评测组织[2,3]推荐的评价度量,它首先计算不同阈值下的准确率(precision)和查全率(recall)并计算该阈值对应的F1值,最后选择最大F1值为Fmax的值.
上述几个度量的形式化定义可参考文献[3,16,21].
对比算法在这4个度量上的值越高,表示其预测质量越好.
从这些度量的定义可知它们从不同的角度评估蛋白质功能预测的质量,一个算法很难在所有度量上均超过另一个算法.
3.
3负样例预测结果分析本小节主要测试分析各个对比算法预测蛋白质负样例的假阴性数和各算法预测的负样例对蛋白质功能预测精度的提升效果.
IFDR分别对蛋白质互作网和蛋白质功能关联矩阵分别进行降维表示,再基于半监督线性回归预测负样例,最终得到n个蛋白质与m个功能标记的关联预测矩阵YmF∈Rn*m.
IFDR从YmF中选取最小的l个元素为预测的负样例,再与2016年更新的蛋白质功能标注数据进行对比,统计预测的假阴性个数FNs.
其他对比算法也通过类似流程分别预测负样例再统计各自的FNs.
表2给出了不同算法在人类数据集(20152016)上的验证结果.
限于篇幅,这些算法在其他数据集上的实验结果报告在补充材料的表S1和S2中.
从这些表中的对比结果不难发现,本文提出的IFDR方法在绝大部分实验设置(不同的l和时间段)下都取得相比其他对比算法更小的FNs.
以人类数据集(20152016)中BP分支的结果为例,在选取80000(l=80k)个预测的负样例做检验时IFDR无假阴性预测,NegGOA产生了2个假阴性预测,ProPN和SNOB分别产生了51个和24个假阴性预测,clusDCA和IFDR-DCA分别产生了189和26个假阴性预测.
通过Wilcoxon符号秩检验[45]统计IFDR和其他对比算法在多个数据集上的负样例预测结果的差异显著性,发现对应p值都小于0.
05.
从上述实验结果分析可知IFDR是一种有效的蛋白质不相关功能预测方法.
SNOB仅基于蛋白质已知的正样例计算标记之间的经验条件概率,再结合蛋白质已知的功能标记预估其他标记也标注到该蛋白质上的概率,选择概率值最低的标记为该蛋白质的负样例.
这类经验条件概率在频率较高的浅层次功能标记间较为可靠,但在频率较低的深层次功能标记间存在较大偏差,而且这些深层(稀疏)标记很有可能是蛋白质的缺失标记(正样例).
此外,与NegGOA一样,它忽略对蛋白质其他特征信息的利用.
因此,它的FNs比IFDR多.
Random通过随机选取未标注到蛋白质的标记为该蛋白质的负样例,它有时候获得了较SNOB更少的FNs.
原因是Random的随机选择有一定的结构性,稀疏标记通常对应GO中深层次节点,它们被随机选择到的概率较大,更有可能被预测为负样例,而这些负样例在更新的蛋白质功能标注数据中较难被验证.
但由于稀疏标记也很可能为蛋白质的缺失正样例,因而Random通常获得较其他对比算法更高的FNs.
NegGOA首先计算标记间的经验条件概率和基于本体结构的标记间条件概率,再结合蛋白质已有的功能标记和标记间条件概率利用重启动随机游预测蛋白质负样例,它通常获得比SNOB和Random更小的FNs.
但NegGOA仅利用了基因本体结构和已有的功能标注信息,并没有利用蛋白质的其1357余国先等:基于降维的蛋白质不相关功能预测表2人类数据集上不同负样例预测数下的假阴性个数(20152016)Table2FNsofH.
sapiensunderdierentnumbersofpredictednegativeexamples.
Negativeexamplesarepredictedbyavailableannotationsin2015,andvalidatedbyupdatedannotationsin2016Datasetl10k20k30k40k50k60k70k80kIFDR00000000IFDR-DCA523232424262626clusDCA447599121139157174189BPProPN324333543445151NegGOA12222222SNOB44121717182024Random3.
947.
9312.
5316.
4220.
0224.
9529.
5633.
14IFDR00112222IFDR-DCA12223333clusDCA81159227276332373423455CCProPN125614151519NegGOA00034446SNOB1818181818182222Random5.
9112.
0217.
2123.
8230.
0135.
1140.
8647.
23IFDR03456888IFDR-DCA11222456clusDCA1215222935404451MFProPN1146536970747676NegGOA00000028SNOB3838383838383941Random1.
824.
276.
488.
3510.
9812.
4513.
6517.
04他特征信息(如蛋白质互作网和氨基酸序列等),同时它也没有对已知的少量负样例加以应用,所以NegGOA通常获得较IFDR大的FNs,部分情况下也获得比ProPN大的FNs.
ProPN根据已知的蛋白质互作信息和蛋白质正负样例信息构建一个符号混合图,在该混合图上进行标记传播预测蛋白质负样例.
ProPN在拟南芥数据集上的FNs比NegGOA,SNOB和Random低,但它在人类和酵母菌数据集上的FNs比其他对比算法高,有时候比基准方法Random还高.
原因是ProPN在进行符号混合图上的标记传播时容易过度传播蛋白质的正负样例信息,降低了负样例预测的精度.
另一个原因是ProPN并没有考虑标记间的层次结构关系,容易误判蛋白质的缺失正样例为该蛋白质的负样例.
IFDR和clusDCA均在蛋白质互作网上进行了成分扩散分析与降维,不同的是clusDCA在GO对应的有向无环图上进行了无向的成分扩散分析和降维,再求解两种低维向量之间的关联映射矩阵R进行负样例预测.
IFDR在蛋白质–功能标记关联矩阵上进行缺失标记预估再对该矩阵进行降维.
clusDCA的FNs总是比IFDR多,也通常比其他对比方法多.
原因是它求取的关联映射矩阵并不一定适合负样例预测问题;另一个原因是它假定未登记的蛋白质与标记间关联为蛋白质的负样例,这种假定误导了后续的负样例预测.
IFDR-DCA与clusDCA一样在蛋白质互作网和GO上进行成分扩散分析再降维,然后将高维蛋白质–功能标记关联矩阵降维到低维向量空间,再利用半监督线性回归预测1358中国科学:信息科学第47卷第10期蛋白质负样例.
IFDR-DCA的FNs远小于clusDCA,这表明本文选用的半监督线性回归可以有效地预测蛋白质负样例,也进一步证实了结合已知的负样例进行负样例预测的有效性.
IFDR-DCA在大部分情况下的FNs比IFDR多,主要原因是IFDR对蛋白质潜在的缺失功能标记进行了预估,降低了判定稀疏标记为负样例的概率,进而提高了负样例预测精度.
本文还基于2014年6月的蛋白质功能标注数据,采用上述类似的方法预处理和设置后预测蛋白质负样例,再用2015年7月更新的蛋白质功能标注数据检验负样例预测性能,对应实验结果汇报在补充材料表S3S5中.
从这些表中的结果可以看到IFDR在大部分对比实验中均获得较其他对比算法更小的FNs,这些表中的结果和结论与时间段(20152016)类似.
这些实验结果进一步证明了IFDR在负样例预测中的有效性.
本文还将IFDR拓展应用到上述3个物种的蛋白质序列数据,并对比分析IFDR分别在蛋白质互作网,序列数据构造的网络,及其与互作网组成的混合网络上的负样例预测结果.
实验收集了UniProt1)(日期:2017–02–20)中相应蛋白质的序列数据,采用BLAST默认设置进行序列相似度计算,保留E值小于10的相似度构造成对蛋白质之间的边连接,再对网络进行归一化处理,保证网络中每个蛋白质与其他蛋白质的边权重总和为1.
对应的实验结果汇报在补充材料的表S6S11中,表中IFDR-Seq仅在序列数据构造的网络上预测负样例,IFDR-Com在混合网络上预测负样例,IFDR仅在互作网上预测负样例.
从这些表中的结果可以看到IFDR-Seq和IFDR-Com与IFDR的FNs在少数情况下有可比的结果,但它们的FNs通常大于IFDR.
这是因为所有成对蛋白质进行序列比对后构造的网络能够比较好地描述成对蛋白质之间功能关联,在该网络上进行成分扩散分析引入了成对蛋白质之间额外的关联,这些额外的关联蛋白质之间原始序列比对的E值大于10,因而IFDR利用序列数据后降低了负样例预测效果.
蛋白质互作网中存在一定的缺失互作和噪声互作,通过成分扩散分析可以挖掘缺失的互作,再通过SVD则可以降低成分扩散分析引入的噪声互作和互作网中已有噪声互作的干扰,进而提高负样例预测效果.
基于上述实验结果,本文在后续实验中仅利用蛋白质互作信息进行负样例选择.
3.
4负样例可提高功能预测精度由于已有蛋白质的功能信息并不完善,统计FNs仅能在一定程度上反映各个负样例预测算法的性能.
研究发现,结合蛋白质负样例进行功能预测可以提高预测精度[24,26,27,31].
为进一步对比分析上述方法预测的负样例,本文基于Youngs等[24]提出的改进GeneMANIA[11]的方法SWSN进行蛋白质功能预测.
SWSN可以同时利用正负样例整合多个蛋白质功能关联网络进行功能预测.
在此部分实验中本文采用Mostafavi等[46]收集整理的Yeast和Human多个功能关联网络数据为数据集,并基于2015的蛋白质功能标记数据标注网络中的蛋白质功能.
SWSN将各负样例预测算法预测的负样例,蛋白质已知的正负样例和多个网络作为输入,优化这些网络对应的权重,并将它们加权合并成一个复合网络,再在复合网络上进行蛋白质功能预测,再用2016年更新的数据检验预测的性能.
通常蛋白质的负样例数远大于正样例数,在此部分实验中本文设置预测的负样例数量为已知正样例的十倍.
Myers等[47]指出特别稀疏的功能标记很难被生物湿实验检验,参考SNOB和NegGOA中的实验设置,实验中不考虑标注的蛋白质个数少于3的标记.
在上述实验设置下,表3列出了各对比算法的预测结果.
由于clusDCA和Random的FNs通常远大于其他对比方法,表3没有包含这2个方法对应的结果.
从表3中可以看到IFDR提供的负样例在大部分情况下都获得较这些对比算法更高的精度,在24个(2物种*4种评价度量*3个GO分支)对比实验中,IFDR分别在70.
8%,75%,79.
2%和91.
7%1)http://www.
uniprot.
org/.
1359余国先等:基于降维的蛋白质不相关功能预测表3酵母菌和人类多网络数据集上的蛋白质功能预测结果Table3ResultsofproteinfunctionpredictiononmultiplenetworksofYeastandHumandatasetsYeastHumanIFDRProPNNegGOASNOBIFDR-DCAIFDRProPNNegGOASNOBIFDR-DCABP0.
85180.
84350.
76220.
76260.
77230.
82120.
81820.
81820.
80990.
7766MacroF1CC0.
74590.
64060.
53810.
50870.
54520.
82210.
81240.
68920.
64730.
6341MF0.
91180.
91040.
82520.
79280.
83230.
85660.
85120.
84080.
83450.
7940BP0.
22920.
21180.
22310.
22190.
22110.
29600.
29050.
29050.
28950.
2922RAccuracyCC0.
42170.
40260.
41920.
38000.
41310.
40940.
40680.
40820.
40090.
4041MF0.
27770.
25000.
27060.
26910.
26940.
47220.
46160.
46760.
44080.
4267BP0.
95930.
96160.
96530.
96970.
91160.
92030.
93050.
93810.
93290.
8845AUCCC0.
97890.
97820.
97970.
98080.
77280.
93600.
94360.
94680.
94420.
8203MF0.
98170.
98010.
98090.
98170.
95050.
94220.
94890.
95280.
94960.
9032BP0.
69020.
77580.
77630.
63880.
70360.
82270.
79150.
81110.
65470.
7710FmaxCC0.
76020.
78700.
80380.
71130.
77170.
78880.
77790.
78780.
71910.
7880MF0.
81450.
79530.
80180.
71540.
80280.
84970.
82710.
83180.
78400.
8388情况下优于NegGOA,ProPN,SNOB和IFDR-DCA;在29.
2%,25%,20.
8%和8.
3%的情况下被这4个对比方法超过;在0%,0%,4.
16%和0%的情况下获得跟它们一样的结果.
本文再次通过Wilcoxon符号秩检验评估IFDR与其他对比算法预测结果的差异性,对应的p值分别为0.
089,0.
034,0.
0008和0.
0002,可见IFDR显著性优于ProPN,SNOB和IFDR-DCA.
IFDR虽与NegGOA的结果相比较显著性并不明显,但也存在一定优势.
从评价度量上可以发现IFDR在MacroF1和RAccuarcy上总能比其他对比算法获得更高的精度.
这一原因是IFDR通过成分扩散分析和SVD降低了假阳性互作的破坏作用,并通过蛋白质–功能标记关联矩阵上的缺失正样例预估和SVD挖掘了蛋白质与标记间潜在的关联,从而针对稀疏标记的负样例预测更加准确,进而帮助SWSN更准确地预测蛋白质功能,特别是蛋白质缺失的功能标记和稀疏标记.
蛋白质的缺失功能标记通常对应蛋白质已知功能标记的子孙节点,是对这些已知功能的进一步细化.
RAccuarcy评估多少缺失的标记被准确预测,MacroF1受稀疏标记的影响更大,因此IFDR选择的负样例能够帮助SWSN获得较其他算法更高的RAccuarcy和MacroF1.
这种实验结果进一步证明了对蛋白质缺失标记进行建模和对蛋白质网络与标记空间进行降维学习与压缩的必要性和有效性.
IFDR在大部分情况下可以取得比其他算法更高的Fmax,但获得的AUC低于其他对比算法.
原因是IFDR通过对蛋白质–功能标记关联矩阵先进行了降维再进行升维,YmF存在较多的非零元素,AUC汇总每个标记在不同阈值下的预测结果,较多的非零元素影响不同阈值下的预测结果,所以IFDR获得的AUC低于其他算法;而Fmax在[0,1]的阈值范围内计算每个阈值对应的F1-score,选择最大的F1-score评价功能预测性能,因此它较少受YmF中非零元素过多的干扰.
综上所述,IFDR不仅能够较其他对比算法更准确地预测蛋白质负样例,IFDR预测的负样例对蛋白质功能预测精度的提升也通常优于这些对比方法.
CAFA(criticalassessmentofproteinfunctionannotationalgorithms)是蛋白质功能预测领域的一个专业比赛[2,3],本文收集了CAFA2的基准数据集(2013.
092014.
09),并整理出了人类、酵母菌和拟南芥3个物种的相关数据(包括序列数据、基因表达数据、结构功能域和互作网),进一步验证本文算1360中国科学:信息科学第47卷第10期表4INGA结合负样例后蛋白质功能预测结果Table4ResultsofproteinfunctionpredictionbyINGAwithout/withusingnegativeexamplespredictedbyIFDRS.
cerevisiaeH.
sapiensA.
thalianaINGAINGA-NegINGAINGA-NegINGAINGA-NegBP0.
15090.
15070.
38190.
38150.
22100.
2212AUCCC0.
20500.
20510.
50300.
50530.
27540.
2711MF0.
18580.
18510.
66340.
66240.
23600.
2393BP0.
53830.
53850.
45580.
45580.
47060.
4703FmaxCC0.
70200.
70860.
55190.
55580.
75290.
7551MF0.
64620.
64700.
57020.
57290.
58400.
5827BP0.
11630.
11270.
08670.
08180.
08420.
0766RankingLossa)CC0.
09490.
09020.
11080.
09120.
03330.
0280MF0.
05470.
05120.
09370.
08570.
17630.
1512BP12.
823712.
821226.
458626.
452314.
04314.
0204Smina)CC5.
18675.
16776.
81486.
80885.
05674.
9987MF4.
29514.
23878.
10878.
09445.
26685.
1093a)Thelowervaluemeansthebetterperformance.
法的有效性.
本文选用CAFA2中2种排名前10的算法INGA[48]和MSkNN[49]检验IFDR选择的负样例对蛋白质功能预测的贡献.
其中INGA分别在蛋白质互作网和结构功能域网络上进行GO富集分析,以及序列同源性进行初步功能预测,再整合这些异构数据源上的预测结果.
MSkNN通过在每种数据上训练一个k近邻分类器,再整合这些分类器的预测结果.
此处,本文参照CAFA2中采用的基准评价度量Smin,Fmax和AUC,同时还引入RankingLoss[16]作为第4种评价度量.
Fmax和AUC在前一节中已经有所介绍,Smin取不同阈值下预测错误标记的结构信息损失和未预测到标记的结构信息损失的最小值,Smin的值越小表示在结构信息上的损失量越小;RankingLoss表示在对每个蛋白质的预测结果进行排序后其不相关标记排在相关标记前的比值.
与Smin类似,RankingLoss值越小表明预测质量越好.
考虑到蛋白质功能的负样例数远大于其正样例数,在此部分实验中本文设置预测的负样例数量为已知正样例的2倍.
表4和补充材料中的表S12分别报告INGA和MSkNN的预测结果和结合IFDR选择的负样例后的预测结果,其中INGA-Neg和MSkNN-Neg分别对应它们结合IFDR选择的负样例后的结果,INGA和MSkNN对应各自原始结果.
从表4和S12中的结果可以发现,INGA-Neg和MSkNN-Neg较INGA和MSkNN在RankingLoss和Smin上都有了较明显的下降,在Fmax上有微量提升或保持近似.
通过Wilcoxon符号秩检验分别统计MSkNN-Neg与MSkNN,INGA-Neg与INGA在这些数据集上的差异性,对应p值分别为0.
048和0.
00035.
上述实验和统计结果表明IFDR预测的负样例能有效地缩小蛋白质功能预测问题规模,提升已有蛋白质功能预测算法的精度.
INGA-Neg(MSkNN-Neg)利用负样例后在评价度量AUC上的提升并不明显甚至有所下降,这是因为INGA-Neg(MSkNN-Neg)预测的蛋白质–功能标记关联概率矩阵中存在较多的非零元素,AUC是一种以标记为中心的度量,它汇总每个标记在不同阈值下的预测结果,较多的非零元素影响其不同阈值下的预测结果.
3.
5降维贡献分析IFDR通过在蛋白质互作网的邻接矩阵和蛋白质–功能标记关联矩阵上分别进行基于SVD的维1361余国先等:基于降维的蛋白质不相关功能预测图1(网络版彩图)人类数据集上降维目标维度影响(d和c分别为蛋白质互作网和标记空间降维的目标维度)Figure1(Coloronline)InuenceofthesizeoftargetdimensionalityonH.
sapiens.
dandcrepresentthetargetdimen-sionalityofPPInetworkandfunctionlabelspace,respectively.
(a)BP;(b)CC;(c)MF数约减,再利用半监督回归进行负样例预测.
本小节探索降维的目标维度对IFDR的影响,令d和c分别表示蛋白质互作网和蛋白质–功能标记关联矩阵降维后的特征维度大小,在本部分实验中将d和c分别从20增加到800,并登记不同d和c组合下IFDR的FNs.
在人类蛋白质数据集上的实验结果(20152016)如图1所示.
从图1中可以发现,总体上随着投影维度的下降,FNs越变越小,但在d=20或c=20时,FNs并不是最小的.
原因是这2类数据均需要一定量的特征描述原始蛋白质之间的互作和蛋白质与功能标记间的关联.
在d>500或c>500时,FNs不断增大,原因是较大的目标维度易引入较多的噪声特征,降低半监督回归的性能从而增大FNs.
在对蛋白质互作网进行降维后,FNs下降比较明显,这是因为蛋白质互作网本身存在一部分噪声互作,虽然成分扩散分析能够在一定程度上降低噪声互作的干扰,但是成分扩散分析本身也会传播噪声互作.
上述观察表明在成分扩散分析更新的邻接矩阵上进行SVD是合理也且必要的.
在蛋白质–功能标记关联矩阵上的降维效果情况与蛋白质互作网相似,FNs随着维度下降而增大.
这一观察表明SVD可以在一定程度上降低预估的假阳性缺失标记的破坏作用.
从图中还可以发现对蛋白质互作网和蛋白质–功能标记关联矩阵分别进行降维压缩表示是有效的.
本文统计了IFDR在上述实验中取得最小FNs时,d和c各应取所有奇异值总和中约前25%和45%的奇异值对应的特征向量实现对网络空间和标记空间的降维.
为了更加深入地分析在蛋白质互作网空间和功能标记空间上降维的贡献,本文基于IFDR衍生出4个变种IFDR-F,IFDR-P,IFDR-FSVD和IFDR-N.
IFDR-F只对蛋白质–功能关联矩阵进行潜在功能标记预估和降维,直接利用原始蛋白质互作网进行负样例预测;IFDR-P只对蛋白质互作网进行成分扩散分析和降维,再在原始标记空间进行负样例预测;IFDR-FSVD在蛋白质互作网上进行成分扩散分析和降维,但仅对蛋白质–功能关联矩阵进行SVD降维.
IFDR-N直接在原始标记空间和蛋白质互作网上进行负样例预测.
在本小节实验中蛋白质互作网和标记空间压缩的目标维度(d和c)均设为300.
限于篇幅,表5仅报告IFDR和4个变种在人类数据集上的实验结果,其他数据集上的实验结果在补充材料的表S13和S14中.
从这些表中数据可以看出,IFDR-N的FNs通常是最高的,这是因为IFDR-N没有对蛋白质的缺失功能标记进行预估,也没有考虑蛋白质之间的噪声互作的破坏作用.
IFDR-P虽然通过成分扩散分析和基于SVD的降维降低了假阴性互作和假阳性互作的影响,但并没有很好地解决蛋白质功能标记的不平衡性和稀疏性,所以它的FNs也相对较高.
IFDR-F的FNs比IFDR-N和IFDR-P更小,说明利用蛋白质已知的功能标记结合基因本体结构对潜在的正样例进行预估,再通过SVD降低错误预估的正样例的破坏作用是有效的.
从IFDR-F与IFDR之间FNs的差值和IFDR-P与IFDR之间1362中国科学:信息科学第47卷第10期表5人类数据集上不同IFDR变种的负样例预测结果Table5ResultsofnegativeexamplespredictiononH.
sapiensbydierentvariantsofIFDRDatasetl10k20k30k40k50k60k70k80kIFDR00000000IFDR-F113513131718BPIFDR-P3063101134160192228264IFDR-N2852120174211259300329IFDR-FSVD77121415152021IFDR00112222IFDR-F01225677CCIFDR-P3488118158228273349440IFDR-N2383124173229293363449IFDR-FSVD0381216161818IFDR03456888IFDR-F711151517202122MFIFDR-P1023496683105124132IFDR-N1226303646535863IFDR-FSVD33344588FNs的差值可知,相对于对蛋白质互作网进行降维,对蛋白质的标记空间进行降维对负样例的预测精度提升作用更大.
IFDR-P的FNs通常小于IFDR-N进一步证实对蛋白质互作网数据进行成分扩散和降维的必要性.
由于实验中统一设置d=300,并没有根据不同物种的蛋白质互作网进行优化,因此IFDR-P有时候获得较IFDR-N高一些的FNs.
IFDR-FSVD实际上是在IFDR-P基础上继续对蛋白质–功能标记关联矩阵降维,它的FNs要少于IFDR-P,与IFDR-F在部分设置下能获得类似的FNs,这说明SVD能在保证正样例标记的特征下,减少噪声对预测结果的影响.
但IFDR-FSVD的FNs通常大于IFDR,这进一步证明对潜在正样例预估可以提升负样例预测的准确性.
上述实验分析证明对蛋白质互作网的邻接矩阵和蛋白质–功能标记关联矩阵进行降维压缩是必要而且有效的,这种处理可以降低负样例预测的假阴性数.
此外,为了分析不同来源的蛋白质互作网数据对IFDR的影响,本文还下载了STRING数据库[50]中的人类和酵母菌的蛋白质互作网络数据,对网络中的蛋白质采用了类似3.
1小节的方法标注,再进行实验.
补充材料的表S15和S16登记了IFDR和上述4变种在STRING数据库上的结果.
这些方法在人类和酵母菌上的结果与BioGrid上结果类似,均表明对网络和标记空间降维可提升负样例预测精度,不同数据库对IFDR的影响很小.
3.
6运行时间分析SNOB需要计算成对标记间的经验条件概率,对应时间复杂度为O(m2),它评估n个蛋白质与m个标记的正负关联性对应的时间复杂度为O(nm2),所以SNOB总的时间复杂度为O(nm2).
NegGOA不仅需要计算成对标记间的条件概率,还需计算标记之间的结构相似度,对应的时间复杂度为O(m2+m3);NegGOA再进行随机游走拓展功能标记之间的关联关系,进而预测蛋白质负样例,此部分的时1363余国先等:基于降维的蛋白质不相关功能预测图2(网络版彩图)对比算法在不同数据集上的运行时间统计Figure2(Coloronline)Statisticsofruntimecostoffourcomparingmethodsondierentdatasets.
(a)H.
sapiens;(b)S.
cerevisiae;(c)A.
thaliana间复杂度为O(nm2);因此NegGOA总的时间复杂度为O(m3+nm2).
ProPN构建和初始化一个包含n+m节点的符号混合图的时间复杂度为O(n2+m2+nm),混合图上标记传播的时间复杂度为O((n+m)2m),因此ProPN总的时间复杂度为O((n+m)2m).
IFDR分别在蛋白质互作网上进行成分扩散分析和在GO对应的有向无环图上进行n个蛋白质的缺失正样例预估,对应的时间复杂度分别为O(n3)和O(nm2),IFDR再分别通过SVD进行奇异值分解降维,这部分的时间复杂度分别为O(n3)和O(min{nm2+n2m});在d维特征空间和c维标记空间上的半监督线性回归的时间复杂度为O(nd2+n2c),由于dn和cm,因此IFDR总的时间复杂度为O(n3+min{nm2+n2m}).
需指出的是蛋白质互作网和基因本体结构对应的邻接矩阵均为稀疏矩阵,故这些算法的实际运行复杂度要低于上述分析结果.
此外IFDR仅需求解前d(或c)个奇异值及其对应的左右特征向量,故IFDR在SVD这一部分的时间运行复杂度也低于理论分析结果.
与3.
3小节的实验设置一样,本文记录了除基准方法Random以外其他算法在不同数据集上的运行时间(5次平均),并报告在图2中.
所有算法均基于Matlab2012b(64bit)实现,实验运行平台配置为:LinuxOS2.
6.
32,IntelXeonE5-2678v3和256GBRAM.
从运行时间上来看,SNOB在CC和MF分支的运行时间最小,但在BP上总是高于IFDR.
这是因为SNOB需要计算m个标记之间的条件概率,其时间复杂度为m的平方,BP中的功能标记个数远大于CC和MF分支.
NegGOA不仅需要计算标间的条件概率,还利用GO结构计算标记间的转移概率,由于标记集合m很大,所以其时间耗费远大于其他对比方法.
虽然ProPN采用一个混合图进行负样例预测,混合图对应的邻接矩阵为n+m的方阵,远大于其他对比方法,但由于对应的邻接矩阵为稀疏矩阵,所以其运行时间总是小于NegGOA,有时跟SNOB的相近.
ProPN利用余弦相似性度量计算标记间的关联关系,再针对m个标记进行负样例预测,所以其运行时间在标记个数多的BP分支总是大于IFDR,在标记个数小的CC和MF分支小于IFDR.
本文提出的IFDR由于利用SVD对蛋白质互作网络和蛋白质功能标记空间分别进行了降维压缩,在功能标记最多的BP分支上的运行时间小于ProPN和SNOB,但在功能标记较少的CC和MF分支上大于这两个方法.
这是因为蛋白质个数远大于MF和CC分支的标记个数,蛋白质互作网上的成分扩散分析和SVD的耗时远大于蛋白质–功能标记关联矩阵上SVD的耗时.
从图2和前2节的实验结果可以发现IFDR算法不仅能较相关算法更准确地预测蛋白质的负样例,还能保持较高的效率,特别在功能标记集合比较大的物种上.
4结束语本文针对蛋白质负样例预测中的正样例信息不完整和标记空间过大等问题,提出一种基于蛋白质1364中国科学:信息科学第47卷第10期互作网和功能标记降维的负样例预测方法(IFDR).
IFDR通过对蛋白质互作网络进行成分扩散分析和对蛋白质缺失正样例进行预估后,再利用SVD对噪声特征鲁棒的特点分别对网络空间和标记空间进行降维压缩,最后采用一个半监督回归方法预测蛋白质负样例.
与现有负样例预测方法相比,IFDR不仅同时利用了蛋白质已知的正样例和少量负样例,还结合成分扩散分析和降维降低了噪声的破坏作用,提高了负样例预测效率和质量.
实验表明,对蛋白质互作网络和功能标记空间进行降维是合理且有效的.
针对降维后数据的特性,本文选用了一个简单的半监督线性回归方法预测负样例,后续研究将探索新的回归方法,进一步提高负样例预测精度.
本文实验中简单设置网络和标记空间的目标维度(d和c)均为300,后续工作将调研如何根据具体的数据集分别设置合适的d和c,探索其他降维方法对IFDR的影响也是一个值得研究的方向.
参考文献1RobertsRJ.
Identifyingproteinfunction—acallforcommunityaction.
PLoSBiology,2004,2:e422RadivojacP,ClarkWT,OronTR,etal.
Alarge-scaleevaluationofcomputationalproteinfunctionprediction.
NatureMethods,2013,10:221–2273JiangYX,OronTR,ClarkWT,etal.
Anexpandedevaluationofproteinfunctionpredictionmethodsshowsanimprovementinaccuracy.
GenomeBiology,2016,17:1–194AshburnerM,BallCA,BlakeJA,etal.
Geneontology:toolfortheunicationofbiology.
NatureGenetics,2000,25:25–295HuntleyRP,SawfordT,MartinMJ,etal.
Understandinghowandwhythegeneontologyanditsannotationsevolve:theGOwithinUniProt.
GigaScience,2014,3:16LeeD,RedfernO,OrengoC.
Predictingproteinfunctionfromsequenceandstructure.
NatureReviewsMolecularCellBiology,2007,8:995–10057DengL,ChenZ.
Anintegratedframeworkforfunctionalannotationofproteinstructuraldomains.
IEEE/ACMTransComputBiologyBioinform,2015,12:902–9138SharanR,UlitskyI,ShamirR.
Network-basedpredictionofproteinfunction.
MolecularSystBiology,2007,3:1–159SchwikowskiB,UetzP,FieldsS,etal.
Anetworkofprotein-proteininteractionsinYeast.
NatureBiotech,2000,18:1257–126110VazquezA,FlamminiA,MaritanA,etal.
Globalproteinfunctionpredictionfromprotein-proteininteractionnetworks.
NatureBiotech,2003,21:697–70011MostafaviS,RayD,Warde-FarleyD,etal.
GeneMANIA:areal-timemultipleassociationnetworkintegrationalgo-rithmforpredictinggenefunction.
GenomeBiology,2008,9:S412Cesa-BianchiN,ReM,ValentiniG.
Synergyofmulti-labelhierarchicalensembles,datafusion,andcost-sensitivemethodsforgenefunctionalinference.
MachLearn,2012,88:209–24113YuGX,ZhuHL,DomeniconiC,etal.
Integratingmultiplenetworksforproteinfunctionprediction.
BMCSystBiology,2015,9:S314YuGX,FuGY,WangJ,etal.
Predictingproteinfunctionviasemanticintegrationofmultiplenetworks.
IEEE/ACMTransComputBiologyBioinform,2016,13:220–23215ValentiniG.
Truepathrulehierarchicalensemblesforgenome-widegenefunctionprediction.
IEEE/ACMTransComputBiologyBioinform,2011,8:832–54716ZhangML,ZhouZH.
Areviewonmulti-labellearningalgorithms.
IEEETransKnowlDataEng,2014,26:1819–183717YuGX,DomeniconiC,RangwalaH,etal.
Transductivemulti-labelensembleclassicationforproteinfunctionprediction.
In:Proceedingsofthe18thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining,Beijing,2012.
1077–108518WuJS,HuangSJ,ZhouZH.
Genome-wideproteinfunctionpredictionthroughmulti-instancemulti-labellearning.
IEEE/ACMTransComputBiologyBioinform,2014,11:891–9021365余国先等:基于降维的蛋白质不相关功能预测19YuGX,DomeniconiC,RangwalaH,etal.
Proteinfunctionpredictionusingdependencemaximization.
In:Proceed-ingsofthe24thEuropeanConferenceonMachineLearning.
Berlin:Springer,2013.
574–58920YuGX,ZhuHL,DomeniconiC.
Predictingproteinfunctionusingincompletehierarchicallabels.
BMCBioinform,2015,16:121YuGX,ZhuHL,DomeniconiC,etal.
Predictingproteinfunctionviadownwardrandomwalksonageneontology.
BMCBioinform,2015,16:27322FuGY,YuGX,WangJ,etal.
Novelprotein-functionpredictionusingadirecthybridgraph.
SciSinInform,2016,46:461–475[傅广垣,余国先,王峻,等.
基于有向混合图的蛋白质新功能预测.
中国科学:信息科学,2016,46:461–475]23SchnoesM,ReamD,ThormanA,etal.
Biasesintheexperimentalannotationsofproteinfunctionandtheireectonourunderstandingofproteinfunctionspace.
PLoSComputBiology,2013,9:e100306324YoungsN,DuncanP,KevinD,etal.
ParametricBayesianpriorsandbetterchoiceofnegativeexamplesimproveproteinfunctionprediction.
Bioinformatics,2013,29:1190–119825WangH,HuangH,DingC.
Function-functioncorrelatedmulti-labelproteinfunctionpredictionoverinteractionnetworks.
JComputBiology,2013,20:322–34326YoungsN,Penfold-BrownD,BonneauR,etal.
Negativeexampleselectionforproteinfunctionprediction:theNoGOdatabase.
PLoSComputBiology,2014,10:e100364427YuGX,RangwalaH,DomeniconiC,etal.
Proteinfunctionpredictionwithincompleteannotations.
IEEEACMTransComputBiologyBioinform,2014,11:579–59128BleiD,NgA,JordanM.
Latentdirichletallocation.
JMachLearnRes,2003,3:993–102229FuGY,WangJ,YangB,etal.
NegGOA:negativeGOannotationsselectionusingontologystructure.
Bioinformatics,2016,32:2996–300430TongHH,FaloutsosC,PanJY.
Randomwalkwithrestart:fastsolutionsandapplications.
KnowlInfSyst,2008,14:327–34631FuGY,YuGX,WangJ,etal.
Proteinfunctionpredictionusingpositiveandnegativeexamples.
JComputSciDev,2016,53:1753–1765[傅广垣,余国先,王峻,等.
基于正负样例的蛋白质功能预测.
计算机研究与发展,2016,53:1753–1765]32CaoM,PietrasCM,FengX,etal.
Newdirectionsfordiusion-basednetworkpredictionofproteinfunction:incor-poratingpathwayswithcondence.
Bioinformatics,2014,30:219–22733ChoH,BergerB,PengJ.
Diusioncomponentanalysis:unravelingfunctionaltopologyinbiologicalnetworks.
In:Proceedingsofthe19thAnnualInternationalConferenceonResearchinComputationalMolecularBiology.
Berlin:Springer,2015.
62–6434WangS,ChoH,ZhaiCX,etal.
Exploitingontologygraphforpredictingsparselyannotatedgenefunction.
Bioinfor-matics,2015,31:357–36435BanerjeeS,RoyA.
LinearAlgebraandMatrixAnalysisforStatistics.
BocaRaton:CRCPress,201436GuoMZ,DaiQG,XuLQ,etal.
Onproteincomplexesidentifyingalgorithmbasedonthenovelmodularityfunction.
JComputResDev,2014,51:2178–2186[郭茂祖,代启国,徐立秋,等.
一种蛋白质复合体模块度函数及其识别算法.
计算机研究与发展,2014,51:2178–2186]37KullbackS,LeiblerRA.
Oninformationandsuciency.
AnnMathStat,1951,22:79–8638PandeyG,MyersCL,KumarV.
Incorporatingfunctionalinter-relationshipsintoproteinfunctionpredictionalgo-rithms.
BMCBioinform,2009,10:139ZhangXF,DaiDQ.
Aframeworkforincorporatingfunctionalinterrelationshipsintoproteinfunctionpredictionalgorithms.
IEEE/ACMTransComputBiologyBioinform,2012,9:740–75340AlterO,BrownPO,BotsteinD.
Singularvaluedecompositionforgenome-wideexpressiondataprocessingandmodeling.
ProcNationalAcademySci,2000,97:10101–1010641ZhuXJ.
Semi-supervisedlearningliteraturesurvey.
ComputSci,2008,37:63–7742BelkinM,NiyogiP,SindhwaniV.
Manifoldregularization:ageometricframeworkforlearningfromlabeledand1366中国科学:信息科学第47卷第10期unlabeledexamples.
JMachLearnRes,2006,7:2399–243443SpirinV,MirnyLA.
Proteincomplexesandfunctionalmodulesinmolecularnetworks.
In:ProceedingsoftheNationalAcademyofSciences,2003,100:12123–1212844Chatr-AryamontriA,BreitkreutzBJ,OughtredR,etal.
TheBioGRIDinteractiondatabase:2015update.
NucleicAcidsRes,2015,43:470–47845WilcoxonF.
Individualcomparisonsbyrankingmethods.
BiometricsBulletin,1945,1:80–8346MostafaviS,MorrisQ.
Fastintegrationofheterogeneousdatasourcesforpredictinggenefunctionwithlimitedanno-tation.
Bioinformatics,2010,26:1759–176547MyersCL,BarrettDR,HibbsMA,etal.
Findingfunction:evaluationmethodsforfunctionalgenomicdata.
BMCGenomics,2006,7:148PiovesanD,GiolloM,LeonardiE,etal.
INGA:proteinfunctionpredictioncombininginteractionnetworks,domainassignmentsandsequencesimilarity.
NucleicAcidsRes,2015,43:134–14049LanL,DjuricN,GuoY,etal.
MS-kNN:proteinfunctionpredictionbyintegratingmultipledatasources.
BMCBioinformatics,2013,14:S850SzklarczykD,FranceschiniA,WyderS,etal.
STRINGv10:protein-proteininteractionnetworks,integratedoverthetreeoflife.
NucleicAcidsRes,2015,43:447–452PredictingirrelevantfunctionsofproteinsbasedondimensionalityreductionGuoxianYU1*,GuangyuanFU1,JunWANG1&MaozuGUO21.
CollegeofComputerandInformationSciences,SouthwestUniversity,Chongqing400715,China;2.
CollegeofElectricalandInformationEngineering,BeijingUniversityofCivilEngineeringandArchitecture,Beijing100044,China*Correspondingauthor.
E-mail:gxyu@swu.
edu.
cnAbstractProteinsarethefoundationformanylifeprocessesandaccuratelyannotatingtheirbiologicalfunctionscansignicantlyboostthedevelopmentoflifesciences.
Currentfunctionpredictionmodelsfocusonemployingtheknowledgethatproteinsperformspecicfunctions(positiveexamples),butignoretheknowledgethatsomefunctionsareirrelevantforaprotein(negativeexamples).
Recentresearchindicatesthatincorporatingnegativeexamplescanreducethecomplexityandimprovetheaccuracyofproteinfunctionprediction.
Inthispaper,weproposeanapproachforpredictingirrelevantfunctionsofproteinsbasedondimensionalityreduction(IFDR).
Initially,IFDRperformsrandomwalksthroughmatricesinaprotein-proteininteractions(PPI)network,aswellasthecorrespondingprotein-functionassociationmatrices,inordertoexploretheunderlyingrelationshipsbetweenproteinsandmodelthemissingfunctionalannotationsofproteins.
Next,IFDRusessinglevaluedecompositiontoprojectthesematricesintolow-dimensionalnumericalmatrices.
Finally,IFDRusessemi-supervisedregressiontopredictnegativeexamplesofproteins.
ExperimentsonS.
cerevisiae,H.
sapiens,andA.
thalianadatademonstratethatIFDRcanmoreaccuratelypredictnegativeexampleswhencomparedtorelatedmethods.
Dimensionalityreductioninthenetworkspaceandlabelspacecanbothimprovetheaccuracyofnegativeexampleprediction.
Keywordsproteinfunctionprediction,positiveandnegativeexamples,PPInetwork,functionlabel,dimen-sionalityreduction1367余国先等:基于降维的蛋白质不相关功能预测GuoxianYUwasbornin1985.
HereceivedaPh.
D.
degreeincomputersciencefromtheSouthChinaUniver-sityofTechnology,Guangzhou,in2013.
HeisanassociateprofessorattheCol-legeofComputerandInformationSci-ence,SouthwestUniversity,Chongqing,China.
Hisresearchinterestsincludedataminingandbioinformatics.
GuangyuanFUwasbornin1993.
HereceivedaB.
S.
degreeincom-putersciencefromSouthwestUniver-sity,Chongqing,in2015.
Heiscur-rentlyaMaster'sstudentattheCol-legeofComputerandInformationSci-ences,SouthwestUniversity.
Hisre-searchinterestsincludemachinelearn-ingandbioinformatics.
JunWANGwasbornin1983.
ShereceivedaPh.
D.
degreeinarticialin-telligencefromtheHarbinInstituteofTechnology,Harbin,in2010.
Sheiscur-rentlyanassociateprofessorattheCol-legeofComputerandInformationSci-ence,SouthwestUniversity,Chongqing.
Herresearchinterestsincludemachinelearninganddatamining,andtheirap-plicationsinbioinformatics.
MaozuGUOwasbornin1966.
HereceivedaPh.
D.
degreeincomputersci-encefromtheHarbinInstituteofTech-nology,Harbin,in1997.
Heisaprofes-sorattheBeijingUniversityofCivilEn-gineeringandArchitecture,Beijing.
Hisresearchinterestsincludebioinformat-ics,machinelearning,anddatamining.
1368