论文研究-基于团渗透和距离限制的蛋白质复合物识别算法.pdf

所需积分/C币:16 2019-09-20 16:56:03 1.13MB .PDF

论文研究-基于团渗透和距离限制的蛋白质复合物识别算法.pdf,  算法CPM (clique percolation method)作为一种有效的识别复杂网络中交叠模块结构的算法在社会网络和生物网络中得到了广泛应用. 但, CPM算法应用于蛋白质相互作用网络时蛋白质复合物识别准确率不高, 且不利于识别规模适中的蛋白质复合物. 为克服CPM算法的不足, 本文通过引入距离限制约束识别的蛋白质复合
第2期 刘杉彬,等:基于团渗透和距离限制的蛋白质复合物识别算法 391 53213 342111 山山042 11212 11000 00000 000000 100010 o00|001 图1团的交叠矩阵识别连通k-团集合示例(k=4)12 22CPM-DR算法 近年来,许多研究发现在生物网络中的许多重要的相关生理生化过程所对应的蛋白复合物的规模都比较 适中,处于5至25之间5.因此,我们更希望将算法CPM产生的规模比较庞大的k-团集合分割成多个比 较稠密的子图,从而获取到更准确、更有效、更全面的具有特定生物意义的蛋白质复合物.例如,图2(a)表 示的是算法CPM在k=3时识别的一个规模为23的蛋白质复合物,在真实蛋白质相互作用网络中应该是3 个相互交叠且规模较小的蛋白质复合物(如图2(b)所示) 图2CPM识别的蛋白质复合物与真实的蛋白质复合物 鉴于蛋白质复合物的相关生物特性,我们需要对CPM算法进行改进以识别蛋白质相互作用网络中规模 适中、准确度高、有效性强且更全面的蛋白质复合物.CPM算法认为蛋白质复合物对应于蛋白质相互作用 网络图中相互连通的若干k-团的集合.在这里,我们引入距离限制约束蛋白质复合物的规模,将蛋白质复合 物看作满足一定距离限制的k-团集合,即k-团集合,其中d代表距离限制参数.首先,我们引入规约图,即 将图G中结点规模不小于k的极大团压缩为一个结点,如果两个极大团之间存在k-1个公共点,则在它们 之间建立一条边,形成图G的规约图G 定义1k4-团集合(k- cliques):给定无向图G及对应的规约图G,连通子图HG,H'((,且H是 H对应于G中的规约子图如果对于任意两个结点(v,)∈H满足l(,)≤d,则称连通子图H为图G的 个k-团集合 其中,l(u,U)指结点u到结点v之间的距离,也就是从结点u到结点v中间经过的最少边数 392 系统工程理论与实践 第32卷 基于k4-团集合定义,我们提出了一种基于团渗透和距离限制的蛋白质复合物识别算法 CPM-DR( (clique percolation method based on distance restriction).算法描述如图3所示 Algorithm: CPM-DR Input: PPl, pararneter k, parameter d Output: k-cliques Process 1. G<Generate graph from the PPI 2. Find maximal cliques with size >k in G; 3. Construct the reduced graph G Condense each maximal clique with size 2 k into a condensed vertex For each pair of maximal cliques do If there are k-1 common vertices between them then Create an edge between the two corresponding condensed vertices 4. Call Finding d-connected subgraph(G, d) 5. Output the identified k-cliques Subroutine: Finding d-connected subgraph(g, d) 1. Compute the degree of each node in G 2. Sort all nodes to queue sa in non-increasing order in terms of degrees; 3. while s≠0do T the neighbor nodes of Q with non-increasing order in terms of degrees while T≠Odo {ν←T; IfD(Quv)≤ d then Q←v 。9三9=T-v; Update(7) cIse t=t-v: 1 Return 2; 1 4. Return the detected d-connected subgraphs 图3CPM-DR算法描述 算法 CPM-DR的输入是蛋白质相互作用信息( protein- protein interactions,PPI),团渗透参数k和距离 限制参数d.算法首先根据蛋白质相互作用信息建立网络图G.然后,从图G中获取到规模不小于k的极大 团.接着,将每个规模不小于k的极大团压缩为一个结点,如果两个极大团之间存在k-1个公共点,则在它 们之间建立一条边,最终建立表示团与团之间相互作用的规约图G.然后,算法CPM-DR在规约图C中 找到任意两个结点之间距离不超过d的连通子图其具体过程是:首先,计算规约图G"中每个结点的度,将 结点按非升序排列,并将其放入队列S中.其次,选择度最大的结点作为种子,放入集合Q中,并且将Q的 邻居结点根据度的大小按非升序排列放在候选集合T中.Q的邻居结点是指集合Q中所有结点的邻居节点 的集合.选择候选集合T中度最大的结点v,若集合Q中任意结点与结点U之间的距离不大于距离限制d, 则将结点扩充至集合Q,且将结点v从候选集合T中删除,更新邻居候选集合T;否则,只将结点v从集 合T中删除.最后,算法根据规约图G中获取的连通子图在网络图G中得到所有的k-团集合 3实验结果及其分析 我们用Perl语言实现了CPM-DR算法,从网站http://angel.elte.hu/clustering/下载了交叠蛋 白质复合物识别工具 CFinder.本文使用的实验数据来源于 Alatf-U-Amin等14和Li等15在BMC Bioin formatics发表的两篇文献.蛋白质相互作用网络包括4546个酵母蛋白质和12319对相互作用标准复 合物数据集包括216个蛋白质复合物,最小的复合物包括2个蛋白质,最大的复合物包括81个蛋白质,平均 每个复合物包括6.31个蛋白质 第2期 刘杉彬,等:基于团渗透和距离限制的蛋白质复合物识别算法 393 31与已知蛋白质复合物比较 算法识别的蛋白质复合物( predicted complexes,Pe)与已知蛋白质复合物( known complexes,Kc)的 匹配程度OS(Pc,Kc)的计算公式4-1如公式所示 OS(Pc, Kc VP×v 其中vPc和ⅣKc分别表示Pc和Kc的规模,讠表示Pc和Kc交集的规模 若两个复合物的匹配程度OS(Pc,Kc)超过给定的阈值,则称这两个复合物匹配.对于标准复合物数据 集中的已知复合物,如果识别出的复合物与之匹配程度OS(Pc.Kc)超过给定威值,则称该已知复合物被标 识,如果OS(PcKc)=1,则称该巳知复合物被完全标识.算法标识的已知复合物数量越多说明算法识别复 合物的能力越强 图4描述了不同匹配阈值下已知复合物被算法 CPM-DR和算法CPM标识的数量图4中 CFinder(k=3) CFinder(k=4)和 CFinder(k=5)分别表示算法CPM在团渗透参数k=3、4、5时标识的已知复合物数量; CPM-DR(k=*,d=2)和 CPM-DR(k=*,d=3)分别表示算法 CPM-DR在团渗透参数k不同取值情况下,距 离限制参数d分別为2和3时标识的已知复合物数量,其中团渗透参数k取值分别为3,4,5.当k取值一 定时,算法 CPM-DR在距离限制参数d=2和d=3时标识的已知复合物数量在不同匹配阈值下均明显高于 算法CHM.从图4可以发现,当团渗透参数k取值越小、,算法CPM-DR标识的已知复合物的能力越强.此 外,当k取值一定时,算法 CPM-DR在距离限制参数d=2和d=3时识别的蛋白质复合物数量基本一致,特 别是当OS(Pc2Kc)≥0.5时识别的蛋白质复合物数量几乎完全相同.算法CPM在k=3时标识的已知复 合物数量最多,随眷k值增大,算法CPM在不同匹配程度阈值下能够标识的已知复合物数量逐渐减少.这 是因为随着k值增大,基本的拓扑单元k-团随之减少,能够识别的蛋白质复合物数量也随之减少. Zhang和 Jonsson等利用CⅣ Tinder分析蛋白质相互作用网络也给出了相同的结论17-18.在本文的实验中,算法OPM 在k=3、4、5时识别出来的蛋白质复合物数量分别为178、61、18.通过引入距离限制,算法 CPM-DR在 距离限制参数d=2和k=3、4、5时识别出来的蛋白质复合物数量分别为248、87、32,而 CPM-DR在距离 限制参数d=3和k=3、4、5时识别出来的蛋白质复合物数量分别为238、81、27.从图4可以看出,算法 CPM-DR标识的已知复合物数量在不同匹配阈值下均明显高于算法CPM. 200 a-CFinder(k-5 160 ★—CPM-DR(k3,d=2 e—CPM-DR(k=4,d=2 140 CPM-DR (k-5, d-2 A-CPM-DR(k=3, d=3 CPM-DR(4. d=3 e-CPM-DR (k-5, d=3) 100 80 60 40 20 0 0.00.1020.30.40.50.60.708091.0 重叠阈值 图4不同匹配阈值下已知复合物被标识的数量 算法 CPM-DR主要是通过引入距离限制约束蛋白质复合物规模,从而识别出与已知复合物匹配程度更 394 系统工程理论与实践 第32卷 高,生物意义更加显著的蛋白质复合物.算法CPM在k=3时识别了一个极其庞大的复合物,该复合物含有 865个蛋白质,4508对相互作用,它包含了蛋白质相互作用网络约1/4的蛋白质结点和1/3的相互作用,且 与已知复合物最佳匹配程度Os(Pc,Kc)远小于.01.我们运用算法CPM-DR,对此复合物进行基于距离限 制参数d=2的分解,共得到了58个蛋白质复合物(图5所示) YLR102C YDR118w SOYFRO36W YBR193c YER022W YDLOO5C YHR107c YKLO58w YHR166c● ●YNL172V YDR507c YIR025W YOR174we GL025 YJR076C YDR392w ●YoR194c ●YGL240w YOR249c ●YK022cYDR308c YLR314 cR002 YILO21w YGR274c YER148w YDLOO8w YYBLO84c YOL135C YGL127c YDL225W YLR127c complex 206 complex197 complex201 complex233 complex247 complex246 complex245 complex244 complex243 complex242 complex241 complex 240 complex239 complex238 complex236 (235 complex234 complex232 complex231 complex230 complex229 complex22B complex227 complex226 complex225 complex224 complex223 complex222 complex221 complex220 complex219 co 18 complex217 complex216 complex215 complex214 complex213 complex212 complex211 complex210 complex209 cor 旦Q,旦。00Q 口QQ complex 200 complex199 complex198 complex196 complex195 complex194 complex193 92 complex 191 complex248 图5算法CPM-DR分解算法CPM所识别的最大复合物所得结果 图5中,算法 CPM-DR识别的规模分别为12、9、6、5的蛋白质复合物与已知复合物最佳匹配程度 OS(Pc,Kc)分别达到0.917、0.559、0.595和1.除此之外,算法CPM所识别的含有865个蛋白质和4508 对相互作用的蛋白质复合物经算法 CPM-DR基于距离限制条件的分解后,在匹配程度OS(Pc,Kc)阈值大 于0.5、0.4、0.3、和0.2的情况下分别得到18、25、35和38个蛋白质复合物.这说明基于距离限制条件的 分解比算法CPM识别的蛋白质复合物更准确,更有效,更全面 3.2算法的特异性和敏感度 算法的特异性( specificity,Sp)和敏感度( sensitivity.Sn)是用来评估蛋白质复合物识别算法的另外两 个重要指标.特异性是指算法识别的蛋白质复合物中识别正确的部分所占比重如公式(2)所示;敏感度 是指已知蛋白质复合物中被算法识别出来的部分所占比重,如公式(3)所示 TP Sp=TP+FP TP+FN 其中TP( true positive)表示算法识别的复合物中与已知复合物匹配程度值OS(Pc,kc)≥0.2的个数,FP ( false positive)等于识别的复合物总数减去TP,FN( false negative)表示已知复合物中没有识别的复合物 与之匹配程度OS(PC,Kc)≥0.2的个数 Li等综合考虑敏感度和特异性两个方面,提出了综合评价F,其计算公式(4)如下 Sn+s 算法 CPM-DR和算法CPM的特异性、敏感度和综合评价F的比较结果如表1所示 第2期 刘杉彬,等:基于团渗透和距离限制的蛋白质复合物识别算法 395 表1算法 CPM-DR和算法CPⅵ敏感度和特异性比较结果— Algorithms Parameter F-measure k=3,d=20.613888890.317580650.49278022 k-3,d=30.576851850.332773110.47184506 CPM-DR K=4,d=20.712643680.376594120.52414802 k=4,d=30.685648920.359685420.49872864 k=5,d=20.737554760.566523160.64082344 k=5,d=30.706296300.515451470.59596828 k=3 0.213592230.247191010.2291666′ CPM k-40.155339810.524590160.23970036 k=5 0.092592590.722222220.16414142 从表1可以看出:算法 CPM-DR在团渗透参数k=3,4,5和距离限制参数d分别为2和3时识别的 复合物的敏感度在0.57以上,说明识别出来的复合物与已知复合物匹配阈值大于等于0.2的数量(P)明 显高于已知复合物在该阈值下没有被标识的数量(FN).TP越大,FN越小,敏感度就越高,说明算法识别 出来的复合物可靠生越高.算法CPM的敏感度最高只有0.21359223.特异性表示的则是算法识别出来的 蛋白质复合物中识别正确的部分所占比重.算法CPM-DR在团渗透参数k=3,4,5和距离限制参数d分别 为2和3识别的复合物的特异性都大于0.3,而算法CPM的特异性都大于0.2,且当k=5时明显高于算法 CPM-DR.虽然算法CPM的特异性高于 CPM-DR,但它识别的复合物中与已知复合物匹配的数量(P)却 远小于算法 CPM-DR.此外,由于目前试验测定的已知蛋白质复合物数据的不完整性,算法识别的蛋白质复 合物中可能存在一定比例的复合物是还未被试验测定但是真实存在的从两个算法的综合评价指标F可以 看出,算法(PM-DR的F值要远高于算法CPM,这说明算法 CPM-DR在识别蛋白质复合物方面较算法 CPM的性能更好 33功能富集性分析 为了进一步分析识别的蛋白质复合物的生物意义,我们计算每个蛋白质复合物对应的P-ulwe.很多研 究者根据超几何聚集分布的P- valuel214来注释识别的蛋白质复合物的主要功能. P-value体现了识别的蛋 白质复合物对某个功能的富集程度,其计算公式(5)为 k-1/P、/N-F value 其中,N表示蛋白质相互作用网络的规模,C表示蛋白质复合物中蛋白质数量,k表示蛋白质相互作用网络中 含有该功能的蛋白质数量.如果P-lwe越小,越接近0,则说明蛋白质复合物能够随机出现这种功能的概率 就越低可能更有生物学意义.一般,将P-01e的最小值对应的功能作为该蛋白质复合物的主要功能.通过 给每个识别的蛋白质复合物赋予P-uawe最小对应的功能,可以预测未知蛋白质的功能.这里计算P-vlue 的蛋白质功能注释信息来源于 Fun Cat 算法 CPM-DR在团渗透参数k=3和距离限制参数d=2时识别的蛋白质复合物共有197个对应的P value都小于0.01,有192个其对应的P- value都小于0.001.而算法CPM在参数k=3时识别的蛋白质复 合物只有128个其对应的P-0lue小于0.01.有121个其对应的P-alue小于0.001.由上述分析可知,算 法 CPM-DR识别具有生物意义的蛋白质复合物的能力远高于算法CPM 从公式5可以看出,P- value的大小与蛋白质复合物的规模密切相关.一般来说,规模较大的蛋白质复合 物的P- value比较小.虽然算法OPM-DR引入距离限制约束了蛋白质复合物的规模,但是它产生的蛋白质 复合物的P- value没有发生显著变化.例如算法CPM识别的一个规模为18的蛋白质复合物的-log(P- Ulve)为26,而算法 CPM-DR将其分解后产生的三个蛋白质复合物的-log(P-ue)分别达到了23、17 和14.表2给出了算法 CPM-DR在d=2时识別蛋白质复合物的一个实例的全部功能注释信息.图5(com plkx197)所示的规模为12的蛋白质复合物的-log(P-lc)是23,其对应的 Fun cat中的功能注释信息 为 Modification by ubiquitination, deubiquitination(14.07.05),.在12个蛋白质中有11个蛋白质具有该功 能,所以我们推测另一个蛋白质YGL240w也很有可能具有该功能.事实上,蛋白质YGL240w已经被证实 具有 protein modification功能.除蛋白质YG计240w外,其他蛋白质都具有 Assembly of protein complexes (14.10)和 ATP binding(16.19.03)这两个功能根据该蛋白质复合物内蛋白质功能的一致性,我们可以推测 YGL240w也很可能具有 Assembly of protein complexes和 atP binding这两种功能 396 系统工程理论与实践 第32卷 表2图5( complex197)对应算法CPM-DR识别的蛋白质复合物的功能注释(数字代号表示功能类别) ORF Protein functional categories YBL084C 10.0301.01.111407.0514.1014.1301.0116.0116.19.03 YDLOOSw 10.03.01.01.1114070514.1014.13.01.0116.0116.19.03 YDRl18w 10.0301.01.111407.05 14.10 14.13.01.01160116.19.03 YFRO36w 10.0301.01.1114.070514.1014.1301.01160116.19.03 YGL20w 10.0301.01.1111.07 11.13.01.0116.01 YHR166c 10.03.0101.1114070514.1014.1301.0116.0116.190342.04 YKL02,2 10.0301.01.111407.05 14.10 14.130101160116.19.03 YLR127C 10.03.0101.1114070514.1014.1301.0116.0116.1903 YNL172w 10.03.01.01.111407.05 14.10 14.13.01.01160116.19.03 YOR219c10.01.09.0510.03.01.01.1111070511.1014.13.01.0116.0116.19.03 YLR102c 10.03.01.01.111407.05 14.10 14.13.01.0116.0116.19.03 YIRO25W 10.03.01.01.1114.07.05 14.1014.1301.0116.0116.19.03 表中各数字代号所表示的功能:01.05.25: regulation of C- compound and carbohydrate metabolisn;10.01.09.05: DNA conformat, ion modification; 10.03.01.01.11: mitosis M phase: 10.03.02: meiosis; 14.07.05: modification hy ubiquitination, deubiquitination; 14. 10: assembly of protein complexes; 14. 13.01.01: proteasomal degradation (ubiq- uitin/proteasomal pathway ) 16.01: protein binding; 16. 19.03: ATP binding; 20.09.07.03: ER to Golgi transport 20.09.07.05: intra Golgi transport; 20.09.07.27: vesicle fusion; 42.04: cytoskeleton/structural proteins; 43.01.03.09 development of asco-basidio- or zygospore 4结论 从大规模蛋白质相互作用~络中有效地识别蛋白质复合物对预测蛋白质功能、解释特定的生物进程具 有重要意义.本文提出了一种基于团渗透和距离限制的蛋白质复合物识别算法(CPM-DR).算法的突出贡献 在于:通过引入距离限制约東蛋白质复合物的规模,有效地兗服了算法CPM应用于大规模蛋白质相互作用 网络时存在蛋白质复合物识别准确率不高、蛋白质复合物规模庞大等缺点.本文提出的CPM-DR算法所标 识的已知蛋白质复合物数量是CPM算法所标识的2倍多,说明算法 CPM-DR较CPM具有更好的蛋白质 复合物识别性能,能够为生物学家进行蛋白质复合物识别和蛋白质功能预测试验提供有价值的参考信息.此 外,与CPM算法比较,本文提出的 CPM-DR算法的综合评价效果更好 参考文献 [1 Garrels J I. Yeast genomic databases and the challenge of the post-genomic eraJ. Funct Integr Genomics, 2002 2(4/5):212237 2 KingA D, Przulj N, Jurisica I Protein complex prediction via cost-based clustering. Bioinformatics, 2004, 20 13-3020. 3 Hartuv E, Shamir R. A clustering algorithm based graph connectivityJ]. Information Processing Letters, 2000 76:175181 4 Girvan M, Newman M E J Community structure in social and biological networksJ. PNAS, 2002, 99: 7821- 7826 5 Newman M E J. Fast algorithm for detecting community structure in networksJ. Phys Rev E, 2004, 69 (6) 066133 6 Radicchi F. Castellano C, Cecconi F. Defining and identifying communities in networks[]. Proc Natl Acad Sci USA,2004,101(9):2658-2663 7 Luo F, Yang Y, Chen C F, et al. Modular organization of protein interaction networks[J. Bioinformatics, 2007, 23(2):207214. 8 Gregory S. An algorithm to find overlapping community structure in networks[C// Proc 1lth European Con- ference on Principles and Practice of Knowledge Discovery in Databases(PKDDO7), 2007: 91-102 9 Pinney J W, Westhead DR. Betweenness-Based Decomposition Methods for Social and Biological Networks(M// BaxterS P, Mardia K, Walls R. Interdisciplinary Statistics and Bioinformatics, Leeds University Press, 2007: 87- 90 [10 Zhang S, Wang R S, Zhang X S. Identification of overlapping community structure in complex networks using fuzzy C-inleaus clustering. Physica A, 2007, 374: 483-490 第2期 刘杉彬,等:基于团渗透和距离限制的蛋白质复合物识别算法 97 11 Li M, Wang J X, Chen J E. A graph-theoretic method for mining overlapping functional modules in protein teraction networks[C// Proceedings of the 4th International Symposium on Bioinformatics Research and Ap plications, LNBI, 2008, 4983: 208-219 12 Palla g, Dernyi I, Farkas I, et al. Uncovering the overlapping community structure of complex networks in nature and society!J. Nature,2005,435(7043):814818. 13 Cho Y R, Hwang W, Ramanmathan M, et al. Semantic integration to identify overlapping functional modules in protein interaction networks[J]. BMC Bioinformatics, 2007, 8: 265 14 Altaf-UI-Amin M, Shinbo Y, Mihara K J, et al. Development and implementation of an algorithm for detection of protein complexes in large interaction networks[J. BMC Bioinformatics, 2006. 7: 207. [15 Li M, Chen J F, Wang J X, et al. Modifying the DPClus algorithm for ident ifying protein complexes based on new topological structures[J. BMC Bioinformatics, 2008, 9: 395 16 Bader G D, Hogue C W. An automated method for finding molecular complexes in large protein interaction networks[J]. BMC Bioinformatics, 2003, 4: 2 17 Zhang $, Ning X, Zhang X s. Identification of functional modules in a PPI network by clique percolation clustering]. Comput Biol Chem, 2006, 30(6):445-451 18 Jonsson P, Cavanna T, Zicha D, et al. Cluster analysis of networks generated through homology: Automatic identification of important protein communities involved in cancer metastatisJ. BMC Bioinformatics, 2006, 7

...展开详情
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐