（计算机应用技术专业论文）蛋白质网络中复合物和功能模块挖掘算法研究.pdf

摘要 在后基因组时代，一个重要的挑战就是系统地分析和全面理解 蛋白质之间是如何通过相互作用来完成生命活动的。从拓扑结构上 分析蛋白质网络的特性，进而探寻蛋白质复合物和功能模块、注释 未知蛋白质功能正成为当前国内外研究的重要焦点。 本文从蛋白质网络拓扑特性分析出发，利用各物种蛋白质网络 所具有的一些共性特征设计了有效的蛋白质复合物和功能模块识别 算法，主要研究工作包括： 应用复杂网络理论和图论技术对不同物种的蛋白质网络进行拓 扑特性分析，包括节点的度分布、度与度的相关性、网络直径、网 络的特征路径长度、边介数、边间隔以及网络的可靠性等，发现了 不同物种的蛋白质网络的一些共性特征，为设计合理的蛋白质复合 物和功能模块挖掘算法提供依据。 针对目前能够获得的蛋白质相互作用数据还不完全，直接从蛋 白质网络中挖掘完备的全连通图( 极大团) 来预测蛋白质复合物具有 很大局限性这一事实，提出了一种基于极大团扩展的蛋白质复合物 识别算法i p c m c e 。该算法不需要其它任何辅助信息，简单有效。 将算法i p c m c e 应用于酵母蛋白质网络，实验结果表明其能够识别 比较多的具有生物意义的蛋白质复合物，且对输入参数不敏感。 基于对已知蛋白质复合物内蛋白质之间的最短距离一般不超过 2 的发现，提出了一种基于距离测定的蛋白质复合物识别算法 i p c d m 。实验结果表明，算法i p c d m 较其它识别蛋白质复合物的 聚类方法更能有效地标识已知蛋白质复合物，并且具有较高敏感度、 特异性和综合评价。特别地，算法i p c d m 对蛋白质相互作用大规 模数据中普遍存在的比例较高的假阳性和假阴性具有很好的健壮 性，能够在蛋白质相互作用数据还不完善且具有较高噪声的情况下 有效地识别蛋白质复合物，可以为生物学家进行蛋白质复合物识别 的实验和进一步研究提供有价值的参考信息。 针对基于介数的层次化聚类算法计算复杂度高，很难应用于大 规模蛋白质网络的不足，引入了局部变量边聚集系数，提出了一种 基于边聚集系数的快速层次聚类算法f a g e c 。为降低算法对噪声 的敏感性，本文应用l o g i s t i c 回归模型对蛋白质相互作用的可靠性进 行评估进而建立加权蛋白质网络，并定义了加权的边聚集系数和功 能模块，提出了应用于加权网络的层次聚类算法h c w p i n 。基于g o 数据库中生物过程、分子功能和细胞成分全部三种注释信息的验证 评估结果表明，算法f a g e c 和h c w p i n 不仅能够有效识别蛋白质 网络中具有生物意义的功能模块，并且可以通过修改参数取值来展 示蛋白质网络中功能模块的层次化组织结构。此外，算法f a g e c 和h c w p i n 的运行效率非常高，随着大规模蛋白质相互作用数据的 不断增加，可以应用于更大规模的蛋白质网络。 针对蛋白质网络中普遍存在的“中心性致死性”法则，提出了 一个图分裂规约模型，并在该模型基础上设计了一种新的交叠功能 模块识别算法o m f i n d e r 。实验结果表明算法o m f i n d e r 能够有效地 识别彼此交叠的功能模块，不同功能模块之间的重叠率约为2 。与其 他识别交叠功能模块的算法比较，算法o m f i n d e r 具有更好的识别性 能，且具有更低的丢弃率。 本文提出的几个聚类算法从不同角度出发，有效地解决了蛋白 质网络聚类过程中存在的一些问题。本文提出的聚类算法不仅运行 效率很高，而且具有很好的聚类效果，识别的蛋白质复合物或功能 模块都从统计意义上被证明是有生物意义的，有效地预测了一定数 量的未知蛋白质的功能，将会对生物实验有指导意义。此外，本文 提出的聚类算法对其它具有相似结构的复杂网络也具有普遍意义。 关键词：系统生物学，蛋白质网络，聚类，蛋白质复合物，功能模 块，蛋白质功能预测 a b s t r a c t i n t h ep o s t g e n o m ee r a ，o n eo ft h em o s ti m p o r t a n tc h a l l e n g e si st o s y s t e m a t i c a l l ya n a l y z e a n d c o m p r e h e n s i v e l y u n d e r s t a n dh o wt h e p r o t e i n sa c c o m p l i s ht h e l i f ea c t i v i t i e sb yi n t e r a c t i n gw i t he a c ho t h e r a n a l y z i n gt h ec h a r a c t e r so fp r o t e i ni n t e r a c t i o nn e t w o r k sb a s e do nt h e t o p o l o g ys t r u c t u r e ，i d e n t i f i y i n gp r o t e i nc o m p l e x e s a n df u n c t i o n a l m o d u l e s ，a n dp r e d i c t i n g t h ef u n c t i o n so fu n k n o w np r o t e i n sa r e b e c o m i n gt h e m o s ti m p r o t a n ti s s u e si nt h ed o m e s t i ca n do v e r s e a s r e s e a r c h e s t h ec h a r a c t e r so ft o p o l o g ys t r u c t u r e si n p r o t e i n i n t e r a c t i o n n e t w o r k sa r es t u d i e df i r s t l y b a s e do nt h ec o m m o nc h a r a c t e r so f d i f f e r e n t s p e c i ep r o t e i n i n t e r a c t i o n n e t w o r k s ，s e v e r a l e f f e c t i v e a l g o r i t h m sf o rd e t e c t i n gp r o t e i nc o m p l e x e so rf u n c t i o n a lm o d u l e sa r e p r o p o s e d t h em a i no r i g i n a lw o r k si n c l u d e ： c o m p l e xn e t w o r kt h e o r ya n dg r a p ht e c h n o l o g ya r ea p p l i e dt ot h e a n a l y s i so ft h et o p o l o g ys t r u c t u r ec h a r a c t e r si nd i f f e r e n ts p e c i ep r o t e i n i n t e r a c t i o nn e t w o r k s ，s u c ha st h ed g r e ed i s t r i b u t i o n ，t h ed e g r e e - d e g r e e c o r r e l a t i o n ，t h en e t w o r kd i a m e t e r c h a r a c t e r i s t i cp a t hl e n g h t h ，e d g e b e t w e e n n e s s ，r a n g e ，a n dt h er e l i a b i l i t y s o m ec o m m o nc h a r a c t e r sa r e d e t e c t e df r o mt h e s ep r o t e i ni n t e r a c t i o nn e t w o r k so fd i f f e r e n ts p e c i e s ， w h i c hc a np r o v i d ef o u n d a t i o nf o rd e v e l p i n gr e a s o n a b l ea l g o r i t h m so f m i n i n gp r o t e i nc o m p l e x e sa n df u n c t i o n a lm o d u l e s a t p r e s e n t ，t h e a v a i l a b l e p r o t e i n - p r o t e i n i n t e r a c t i o n sa r en o t c o m p l e t e o n l ym i n i n gm a x i m a lc l i q u e sa r et o ol i m i t e dt ob eu s e df o r p r e d i c t i n gp r o t e i nc o m p l e x e ss i n c ei t i su n l i k e l yt h a ta l lp r o t e i n si na l a r g ec o m p l e xc a ni n t e r a c tw i t he a c ho t h e r t oa v o i do ft h el i m i t a t i o n ，a n e wa l g o r i t h mo fi d e n t i f y i n g p r o t e i nc o m p l e x e sb a s e do nm a x i m a l c l i q u ee x t e n s i o n ( i p c - m c e ) i sp r o p o s e d ，w h i c h i s e a s y t ob e i m p l e m e n t e da n de f f e c t i v e t h ea l g o r i t h mi p c - m c e i sa p p l i e dt ot h e p r o t e i ni n t e r a c t i o nn e t w o r ko fs a c c h r o m y c e sc e r e v i s i a ea n di d e n t i f i e s i i i m a n yw e l lk n o w np r o t e i nc o m p l e x e s m o r e o v e r , a l g o r i t h mi p c - m c e i s n o ts e n s i t i v et ot h ei n p u tp a r a m e t e r b a s e do no u rd i s c o v e r yt h a tm o s to ft h es h o r t e s tp a t h sb e t w e e n p r o t e i n s i n c o m p l e x e s a r en om o r et h a nt w o ，w ep r o p o s ean e w a l g o r i t h mi p c d mf o ri d e n t i f y i n gp r o t e i nc o m p l e x e so nt h eb a s i so f d i s t a n c em e a s u r e t h ee x p e r i m e n tr e s u l t ss h o wt h a tt h ea l g o r i t h m i p c d mr e c a l l sm o r ek n o w nc o m p l e x e st h a no t h e rp r e v i o u s l yp r o p o s e d c l u s t e r i n ga l g o r i t h m sa n dh a sar e l a t i v e l yh i g h e rs e n s i t i v i t y , s p e c i f i c i t y a n df m e a s u r e m o r e o v e r , t h ea l g o r i t h mi p c d mi sr o b u s tt ot h ek n o w n h i g h r a t eo ff a l s e p o s i t i v e s a n df a l s e n e g a t i v e s i nd a t af r o m h i 曲- t h r o u g h o u ti n t e r a c t i o nt e c h n i q u e s t h u s ，t h ea l g o r i t h mi p c d m c a nb eu s e di np r o t e i ni n t e r a c t i o nn e t w o r ke v e nw i t hh i g hf a l s ep o s i t i v e s a n dh i g hf a l s en a g a t i v e st oi d e n t i f yn e wp r o t e i nc o m p l e x e sa n dt o p r o v i d er e f e r e n c e sf o rb i o l o g i s t si nt h e i rr e s e a r c ho np r o t e i nc o m p l e x e s t h eh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m sb a s e do nb e t w e e n n e s sa r e n o ts u i t a b l et ob eu s e di nl a r g ep r o t e i ni n t e r a c t i o nn e t w o r k sb e c a u s et h e y a r et i m ec o n s u m i n g an e wl o c a lv a r i a b l eo fe d g ec l u s t e r i n gc o e f f i c i e n t i si n t r o d u c e da n dan e wf a s th i e r a r c h i c a lc l u s t e r i n ga l g o r i t h mf i a g e c b a s e do ni ti sp r o p o s e d t od e c r e a s et h ee f f e c to fn o i s yd a t ao nt h e c l u s t e r i n gr e s u l t s ，a n e wa l g o r i t h m h c - w p i n i s p r o p o s e d f o r h i e r a r c h i c a l l yc l u s t e r i n gi nt h ew e i g h t e dp r o t e i ni n t e r a c t i o nn e t w o r k t h el o g i s t i cr e g r e s s i o n b a s e ds c h e m ei su s e dt oa s s i g ne a c he d g ea w e i g h t t h ee d g ec l u s t e r i n gc o e f f c i e n ta n dt h ef u n c t i o n a lm o d u l ei n w e i g h t e dg r a p ha r er e d e f i n e d a l lt h ei d e n t i f i e df u n c t i o n a lm o d u l e sa r e v a l i d a t e db yt h et h r e et y p e so fa n n o t a t i o n so fg e n eo n t o l o g y ( g o ) ： b i o l o g i c a lp r o c e s s ，m o l e c u l a rf u n c t i o n ，a n dc e l l u l a rc o m p o n e n t t h e e x p e r i m e n t r e s u l t ss h o wt h a t a l g o r i t h mf a g e ca n da l g o r i t h m h c w p i nc a l ln o to n l yd e t e c tt h es i g n i f i c a n tf u n c t i o n a lm o d u l e si n p r o t e i ni n t e r a c t i o nn e t w o r kb u ta l s oa c c u r a t e l yi d e n t i f y f u n c t i o n a l m o d u l e si nh i e r a r c h yb yc h a n g i n gt h ev a l u e so fp a r a m e t e r m o r e o v e r , a l g o r i t h mf a g - e ca n da l g o r i t h mh c w p i na r ee x t r e m e l yf a s t ，w h i c h c a nb eu s e di ne v e nl a r g e rp r o t e i ni n t e r a c t i o nn e t w o r k so fo t h e r i v h i g h e r - l e v e lo r g a n i s m sa st h ep r o t e i n p r o t e i ni n t e r a c t i o n sa c c u m u l a t i n g s h a r p l y a c c o r d i n gt ot h e “c e n t r a l i t y l e t h a l i t yr u l e g e n e r a l l ye x i s t i n gi n p r o t e i n i n t e r a c t i o nn e t w o r k s ，ag r a p h s p l i t a n dr e d u c t i o nm o d e li s p r o p o s e da n dan e wa l g o r i t h mo m f i n d e rf o ri d e n t i f y i n go v e r l a p p i n g f u n c t i o n a lm o d u l e sb a s e do nt h ep r o p o s e dm o d e li s d e v e l o p e d t h e e x p e r i m e n t r e s u l t ss h o wt h a t a l g o r i t h mo m f i n d e rd e t e c tm a n y s i g n i f i c a n to v e r l a p p i n g f u n c t i o n a lm o d u l e s t h e o v e r l a p p i n g r a t e b e t w e e nd i f f e r e n tf u n c t i o n a lm o d u l e si sa b o u t2 c o m p a r e dt oo t h e r a l g o r i t h m sf o rd e t e c t i n go v e r l a p p i n gf u n c t i o n a lm o d u l e s ，a l g o r i t h m o m f i n d e rh a sb e t t e rp e r f o r m a n c ea n dl o w e rd i s c a r dr a t e t h ec l u s t e r i n ga l g o r i t h m sp r o p o s e di nt h i sp a p e rs t a r to f ff r o m d i f f e r e n ts i g h t sa n ds o l v es o m ep r o b l e m se f f e c t i v e l yi nt h ep r o c e s s e so f c l u s t e r i n g i n p r o t e i n i n t e r a c t i o nn e t w o r k s t h ep r o p o s e dc l u s t e r i n g a l g o r i t h m sn o to n l yc a nb ei m p l e m e n t e de f f i c i e n t l ya n dh a v eg o o d c l u s t e r i n gp e r f o r m a n c e s t h ei d e n t i f i e dp r o t e i nc o m p l e x e so rf u n c t i o n a l m o d u l e sa r ep r o v e dt ob es t a t i s t i c a l l ys i g n i f i c a n t an u m b e ro fu n k n o w n p r o t e i nf u n c t i o n sa r ep r e d i c t e d ，w h i c hc a np r o v i d es o m er e f e r e n c e sf o r b i o l o g i s t si nt h e i rb i o c h e m i c a le x p e r i m e n t s m o r e o v e r ，t h ep r o p o s e d c l u s t e r i n ga l g o r i t h m sc a nb eg e n e r a l i z e dt oo t h e rc o m p l e xn e t w o r k sw i t h t h es i m i l a rs t r u c t u r e s k e yw o r d s ： s y s t e m sb i o l o g y , p r o t e i ni n t e r a c t i o nn e t w o r k ， c l u s t e r i n g ，p r o t e i nc o m p l e x ，f u n c t i o n a lm o d u l e ，p r e d i c t i o no fp r o t e i n f u n c t i o n v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：左熟 日期：j 翌垦年旦月上日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：互楚导师签名：避e tl l ：趟年卫月仁日 博士学位论文 第一章绪论 1 1 蛋白质网络 第一章绪论 随着人类基因组计划和许多物种全基因组测序的完成，生命科学研究的重 点已经逐渐从基因组学转移到了蛋白质组学【i 2 】。蛋白质是由多种氨基酸按特定 的排列顺序通过肽键连接成有一定结构的高分子化合物，它是构成一切细胞和 组织结构必不可少的成分，是生命活动最重要的物质基础1 3 j 。但是，细胞中的 每个蛋白质并不是孤立存在的，而是与其它蛋白质一起进行相互作用来行使其 功能的【4 。5 l 。蛋白质相互作用在生命活动中起核心作用，不仅是正常生理过程如 d n a 复制、转录、翻译、物质代谢、信号传导以及细胞周期控制的基础，也在 病理过程中起着重要的作用【6 9 1 。可以说，几乎所有的生物过程都是通过蛋白质 问的相互作用来精确地执行的。一个生物体内所有蛋白质相互作用被称为蛋白 质相互作用网络( p r o t e i n p r o t e i ni n t e r a c t i o nn e t w o r k ) 【1 0 】，简称蛋白质网络。 近年来，随着酵母双杂交【ij , j 2 、串联亲和纯化【1 3 15 1 、质谱分析【1 6 l 、蛋白质 芯片【1 7 】和噬菌体显剥1 8 1 等高通量蛋白质组技术的发展，可获得的蛋白质相互作 用数据迅速增长，大量的蛋白质相互作用数据已经被收集整理在不同的公共数 据库中，为我们深入研究蛋白质网络打开了方便之门。例如，包含多个物种的 蛋白质相互作用数据库d i p ( d a t a b a s eo fi n t e r a c t i o np r o t e i n s ) 1 1 9 】，提供蛋白质功 能注释信息的慕尼黑蛋白质序列信息中心m i p s ( m u n i c hi n f o r m a t i o nc e n t e rf o r p r o t e i ns e q u e n c e s ) 1 2 0 1 ，来自高通量的数据提交和手动从科技文献中整理得到的 分子相互作用数据库b i n d ( b i o m o l e c u l a ri n t e r a c t i o nn e t w o r kd a t a b a s e ) 1 2 1j ，相互 作用综合数据库g r i d ( g e n e r a lr e p o s i t o r yf o ri n t e r a c t i o nd a t a ) 2 2 】，相互作用的蛋 白质和基因的研究工具s t r i n g ( s e a r c ht o o lf o rt h er e t r i e v a lo fi n t e r a c t i n g g e n e s p r o t e i n s ) 口引，以及酵母蛋白质相互作用数据库y p d ( y e a s t p r o t e i n d a t a b a s e ) t 2 4 】、人类蛋白质相互作用数据库h p i d ( h u m a np r o t e i n i n t e r a c t i o n d a t a b a s e ) t 2 5 l 等。 当前对蛋白质网络的分析和研究主要集中在以下几个方面： ( 1 ) 蛋白质相互作用的评估和预测。 博士学位论文 第一章绪论 随着2 0 0 0 年酵母大规模蛋白质网络图谱的成功描绘，蛋白质相互作用特 别是大规模蛋白质相互作用的研究成为生命科学领域的又一个研究热点【2 6 j 。目 前已开发出多种实验技术和计算方法能够得到大规模蛋白质相互作用数据。例 如，前面提到的酵母双杂交、串联亲和纯化、质谱分析、蛋白质芯片等实验技 术。此外，基于基因的系统发生谱【2 7 1 、基因邻域保守性【2 8 】、基因融合现象 2 9 - 3 0 、 镜像树【3 1 】3 1 、突变关联【3 2 - 3 3 以及基于图理论【3 4 拼】等利用计算机处理数据的计算方 法也被广泛用于蛋白质相互作用的评估和预测。 但是，每一种实验技术或计算方法预测出来的蛋白质相互作用数据都不可 避免地具有一定程度的假阳性和假阴性【3 引。假阳性是指能够被实验技术检测到 的、但在细胞中并不存在的蛋白质相互作用；假阴性是指不能被实验技术检测 到的、但在细胞中确实存在的蛋白质相互作用【3 9 1 。引起假阳性和假阴性的主要 原因【删有：( a ) 实验或计算过程中产生的错误。( b ) 实验技术或计算方法自身的 局限性。每一种实验技术或计算方法所依据的生物学原理不同，其预测的结果 只能部分地描述真实的相互作用，具有技术上的某些偏向性或缺陷，从而导致 错误的预测。( c ) 蛋白质相互作用的动力学本质。在不同生物学条件下，蛋白质 表达和相互作用的模式是不同的。而目前几乎所有的实验技术和计算方法都不 能做到动态预测。 基于以上三个因素可以看出，不仅不同方法预测得到的蛋白质相互作用数 据差异性很大，并且不同的实验室应用相同的方法也很难得到完全相同的蛋白 质相互作用数据。例如，v o nm e t i n g 等【4 1 】比较分析了不同来源的蛋白质相互作 用大规模数据，包括酵母双杂交分析、蛋白质复合物的质谱分析、遗传相互作 用、相关的m r n a 表达以及通过基因组分析进行计算预测等。他们分析的结果 表明，在近8 0 0 0 0 对蛋白质相互作用中，只有约3 的蛋白质相互作用是能够被 2 种或2 种以上方法检测到。而u e t z 等【1 2 】和i t o 等【4 2 】均采用酵母双杂交技术预 测蛋白质相互作用的结果的差异性则说明了不同实验室应用相同技术得到的数 据差别也很大。u e t z 等预测的结果和i t o 等预测的结果中只有1 4 1 对相互作用 是相同的，而这两个结果鉴定的蛋白质相互作用不到前人已发表的1 5 4 3 1 。 因此，为了有效利用这些蛋白质相互作用数据，发现其潜藏着的具有生物 学意义的信息，需要研究有效的方法来评估蛋白质相互作用。目前对蛋白质相 互作用数据中假阴性和假阳性的评估主要是根据已有的相关蛋白质的功能、亚 细胞定位、代谢途径、功能注释以及蛋白质复合物相关信息来进行评估【l 川。 2 博士学位论文 第一章绪论 将不同来源的蛋白质相互作用数据进行整合也是提高蛋白质相互作用的可靠性 的有效手段之一。s n e l 等 2 3 1 构建的s t r i n g 数据库就是将几种计算方法进行整 合来鉴定蛋白质相互作用的。此外，文献也是用来评估由大规模技术产生的蛋 白质相互作用的一个有价值资料 4 4 1 。 ( 2 ) 蛋白质网络的拓扑结构研究。 近年来，科学家们发现大量的真实网络既不是随机网络，也不是规则网络， 而是具有与这两者截然不同的统计特性的网络，其中最具影响的是小世界网络 和无尺度网络。小世界网络模型【4 5 】和无尺度网络模型【舶】的出现，引发了全球对 复杂网络的研究热潮。蛋白质网络已经被证明具有小世界特性和无尺度特性 【4 7 。5 0 】。网络的小世界特性主要表现为具有高的聚集系数( c l u s t e r i n gc o e f f i c i e n t ) 和 低的特征路径长度( c h a r a c t e r i s t i cp a t hl e n g t h ) 。而网络的无尺度特性则主要表现 为增长( g r o w t h ) 和偏好连接( p r e f e r e n t i a la t t a c h m e n t ) 两个特性。增长特性表明无尺 度网络可以不断的扩张，偏好连接特性则意味着两个节点的连接能力的差异可 以随着网络的扩张而增大。研究者应用分形几何和统计物理方法对真核细胞酵 母和细菌幽门螺杆菌进行研究，发现这两种迥然不同的蛋白质网络都具有无尺 度网络特性，网络中大部分蛋白质只与其他一、两种蛋白质发生相互作用，但 有几种蛋白质分子却能与大量的其他蛋白质相结合，所有蛋白质的节点度服从 幂规律分布( p o w e r 1 a wd i s t r i b u t i o n ) s q 。分析表明，个蛋白质参与的相互作用 越多，这个蛋白质对细胞的生存也就越重要。j e o n g 等【5 2 】发现了蛋白质网络的 中心性致死性法贝l j ( c e n t r a l i t y 1 e t h a l i t yr u l e ) 。基于这一特性，研究者可以利用蛋白 质网络来预测关键蛋白质，也称为本质蛋白质( e s s e m i a lp r o t e i n ) 5 3 - 5 5 为进一步解释蛋白质网络中出现的动力学特性，一些网络生长和进化模型 被提出【5 6 - 5 7 1 。其中，最重要的两种进化过程是基因的变异和基因的复制与分化。 基因的变异可以引起蛋白质的相互作用界面发生变化，进而导致相应的蛋白质 失去原有的相互作用，或重新与其他蛋白质建立新连接。而基因的复制就相当 于在网络中增加了一个复制的节点，它和被复制的节点具有相同的相互作用关 系。后续的分化会渐渐地增大复制的节点和被复制的节点的相互作用的拓扑差 异性。e i s e n b e r g 等【5 8 】研究发现蛋白质的进化历史与其所参与的相互作用的数目 之间成正相关。b e r g 等【5 6 】通过对实际数据的分析发现由基因的变异引起的拓扑 变化要远远高于基因的复制和分化。 研究证明，蛋白质网络、代谢网络、基因调控网络等生物网络都存在着明 3 博士学位论文第一章绪论 显的模块化结构【5 9 - 6 3 】。整个蛋白质网络的构成可以抽象成一个复杂的金字塔【6 4 1 ， 塔底是蛋白质，接着是由蛋白质组成的重复出现的基本模式，通常称为基序 ( m o t i f ) ，而基序又可以整合成功能模块( f u n c t i o n a lm o d u l e ) ，执行独立的细胞功 能，最后这些功能模块再以层次嵌套的方式构成蛋白质网络，即塔顶。 ( 3 ) 挖掘网络基序( n e t w o r km o t i f ) 网络基序是各种生物网络的基本组成单元。目前，对生物网络基序还没有 统一的标准定义，最常用的是m i l o 等【6 5 】引入的，他们将网络基序定义为在生物 网络中重复发生的某些连通子图，从统计意义上讲，这些连通子图在该生物网 络中出现的频率比在对应的随机网络中出现的频率高。要求对应的随机网络与 真实的生物网络具有相同的节点度分布特性。 目前，主要的基序挖掘算法有枚举法【6 5 】、取样法 6 6 - 6 7 1 和e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 法1 6 s l ，常用的基序挖掘工具有m f i n d e r t 6 9 、p a j e k l 7 们、 m a v i s t o t 7 1 1 和f a n m o d t 7 2 1 。在大规模相互作用网络中挖掘基序的计算量很大。 例如，典型的基序模型k - p a t h ，即包含k 个节点的简单路径，目前最好的精确 算法的时间复杂度为0 ( 4 旧矿4 2 ) 1 7 3 l 。h u f f n e r 等提出的随机化方法【7 4 】可以在几 秒中内识别包含1 3 个蛋白质的简单路径。而一般的计算方法常常用于挖掘不超 过8 个蛋白质的基序。 研究表明，很多基序在网络的进化过程中是保守的，特别是规模在2 到5 之间的基序具有更高的保守率。例如，完全连通的5 个节点的基序在酵母蛋白 质网络中的保守率为4 7 2 4 ，而在随机网络中的保守率仅有0 0 2 1 7 5 i 。对网络 基序的研究为我们揭示生物网络的进化机制提供了有效手段【| m 7 9 】。 ( 4 ) 挖掘蛋白质复合物( p r o t e i nc o m p l e x ) 和功能模块( f u n c t i o n a lm o d u l e ) 。 蛋白质复合物是指在相同时间和空间通过相互作用组成一个多分子机制的 一组蛋白质，例如转录因子复合物和r n a 拼接等：而功能模块的组成蛋白质则 是在不同的时间和空间通过相互绑定来参与某一特定的分子进程【8 们。目前，关 于两者之间关系的讨论还非常有限，从一般意义上说，功能模块包含蛋白质复 合物。近年来，n a t u r e 杂志上发表了多篇识别蛋白质复合物的学术论文 1 4 - 1 6 , 8 1 - 8 2 】。 这些论文首先通过化学实验测定，然后再对实验测定的结果应用生物信息学方 法进行统计分析。通过化学实验可以较准确地测定某一环境下的蛋白质复合物， 特别是那些比较稳定的复合物。但仍存在一定数量的不稳定复合物，复合物内 的蛋白质之间的相互作用是瞬时的，动态变化的，以实验为基础的研究方法很 4 博士学位论文 第一章绪论 难捕捉到这些蛋白质复合物，而且实验成本十分昂贵。 越来越多的证据【5 9 - 6 3 1 表明，蛋白质网络是由若干相互之间存在一定联系的 蛋白质复合物( 或功能模块) 组成的，而这些蛋白质复合物( 或功能模块) 又是由若 干个蛋白质共同作用而组成来行驶某些功能的。目前，普遍的做法是将蛋白质 网络表示成一个图，利用各种图聚类算法来挖掘蛋白质复合物或功能模块。从 相互作用网络中挖掘蛋白质复合物和功能模块，不仅有利于分析蛋白质网络的 拓扑结构，进而探索蛋白质通过相互作用完成生命活动的奥秘，而且对预测未 知蛋白质功能及蛋白质相互作用也具有极其重要的作用。 本章的第1 3 小节相关工作研究将对蛋白质网络的复合物和功能模块挖掘 算法进行分类综述。 ( 5 ) 预测蛋白质功能。 在蛋白质组学的研究中，一个重要的挑战就是对那些不能应用同源预测方 法进行功能注释的蛋白质进行注释，而应用蛋白质相互作用信息对未知蛋白质一 预测其可能的功能，是一种非常重要的非同源方法【3 9 , 8 3 - 8 6 。目前，已经开发出 多种基于蛋白质网络的功能预测方法。应用最早的也是最简单的方法是主要连 接数方法【8 3 l ，该方法原理很简单，如果某个功能未知的蛋白质连接的其他蛋白 质都具有相同的功能，则这个功能未知的蛋白质也具有此功能，如果其他蛋白 质中的绝大多数具有某一相同功能，则这个功能未知的蛋白质很可能具有此功 能。但是该方法的缺点是不能预测相互作用的两个未知蛋白质的功能，而且如 果连接的其他蛋白质分属于不同功能的个数相同，也很难对该蛋白质进行功能 预测。为此h i s h i g a k i 等【8 7 】提出了一种对邻近的几个蛋白进行统计的方法，而不 只用与之有直接相互作用的蛋白质，但这个距离的度很难把握。随后z h o u 等悼副 提出一种应用表达谱之间的相关性得到网络图中的最短距离来预测蛋白质功能 的方法。上述方法主要是根据蛋白质网络的局部特性进行功能预测。这种局部 预测方法简单实用，准确率较高，但覆盖率较低。 d e n g 等【8 9 】基于马尔可夫随机模型，应用贝叶斯方法对未知蛋白质赋予某个 功能给一个概率，即可信度。v a z q u e z 等1 9 0 l 应用模拟退火算法，对整个网络中 的未知蛋白质赋予功能。k a r a o z 等【9 l j 在整合了基因表达数据的基础上应用 h o p f i e l d 网络技术的局部阈值原则使得整个网络达到一个稳态，对整个网络中 的未知蛋白都进行功能预测。这种全局的预测方法可以对整个网络中所有的未 知蛋白质进行功能预测，提高了覆盖率。但这种从总体上进行平衡的方法必然 5 博士学位论文 第一章绪论 以降低准确率为代价。 此外，蛋白质复合物和功能模块挖掘算法也可以用来预测蛋白质功能。这 类方法主要通过挖掘的子图中已知蛋白质功能的相关性来预测整个子图中蛋白 质所具有的功能。例如，d u n n 等【9 2 l 提出用基于边介数的聚类方法先获得一系列 的子图，然后通过子图中已知蛋白质功能的相关性来预测整个子图中蛋白质所 具有的功能；卢宏超等1 9 3 】从功能模块的定义出发，考虑功能模块之间一阶和二 阶相互作用，通过定义功能模块间的相似度进行聚类分析，进而预测模块内未 知蛋白质的功能。 ( 6 ) 两个或多个蛋白质网络比对。 随着不同物种以及不同类型的细胞网络的出现，研究者们的研究兴趣开始 从序列比对向网络比对转移。从概念上讲，网络比对就是对两个或多个网络进 行比较，而这些网络可能是不同物种的网络，或者是不同生理条件下的网络， 也可能是不同类型的网络，或者是不同时间点上的网络【9 4 j 。而蛋白质网络比对， 重点是不同物种或不同时间点上的蛋白质网络的比较，目的在于发现保守的复 合物和功能模块。最早，m a t t h e w s 等【9 5 】通过比较不同物种的蛋白质网络来识别 直系同源的蛋白质节点之间保守的相互作用，称为i n t e r o l o g s ( i n t e r a c t i o n s c o n s e r v e di no r t h o l o g s ) 。k e