（计算机应用技术专业论文）生物网络中大模体识别算法的研究.pdf

r e s e a r c ho nt h e a l g o r i t h m sf o r d i g 。7 7 m o t i fi nb i o ig d i s c o v e r i n g l a r g e r o t t ti nb i o l o g i c a l i n e t w o r k s m a y 2 0 1 0 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名： 乃曲7 日期：址石哆 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 研究生签名：地师签名： 日期：造! ! 够 摘要 近年来，随着生物技术，尤其是高通量技术的发展，生物网络数据有了显著的增长，出 现了很多的生物网络数据库，包括蛋白质反应网络，新陈代谢网络，基因调控网络，神经网 络等，如何从这些浩瀚的生物网络中识别出与功能相关的结构是当前的一个研究热点，而如 何从生物网络识别出模体是研究生物网络结构和功能的关键一步。模体是指在某个网络的多 个不同部分出现的某一相互连接的子结构，其表达程度明显高于在随机网络中的表达。 目前的模体识别方法主要有穷举法和抽样法，前者试图找出给定真实生物网络中指定大 小的所有模体，然而随着子图的增大，候选子图的数量呈爆炸性增长，识别模体所需的时间 急剧增长，同时，内存空间也呈爆炸性增长，程序很快因内存空间耗尽而崩溃，所以穷举模 体识别方法只能识别小规模和中等规模的模体，面对稍大规模的模体无能为力。针对此问题， 抽样模体识别方法应运而生，抽样法降低了穷举法因为遍历访问子图空间而产生的高复杂度， 该类方法部分访问子图空间，显著地降低了时间复杂度和空间复杂度，但由于难以等比例抽 样，产生了抽样偏置，以及调整该偏置而产生的额外计算复杂度，同时抽样模体识别方法还 存在抽样概率难以精确分配的缺陷。 针对这些问题，本文在传统的模体识别方法上进行了研究和拓展，首先提出了一种基于 划分的子图搜索算法( p a r t i t i o nb a s e ds u b g r a p hf i n d e r ，p s g f ) ，该算法能够唯一，不遗漏， 高效地搜索给定真实生物网络中指定大小的所有子图，p s g f 基于划分的思想，即任意两颗搜 索树中的子图通过全局划分顶点来加以区分，同一棵搜索树中不同子树中的子图通过局部划 分项点来加以区分，从而能够实现不重复性。p s g f 在运行过程中仅仅在内存中维持一条搜索 树中从根结点到叶结点的路径，所以具有较小的内存使用量。本文将p s g f 应用到模体识别框 架中，产生了一种新的穷举模体识别方法基于划分的模体识别算法( p a r t i t o nb a s e d n e t w o r km o t i ff i n d e r ，p n m f ) ，在u e t z 数据集上成功识别了中等规模的模体，与同类方法相 比，具有较小的时间复杂度和空间复杂度。针对抽样模体识别方法概率值难以精确分配的缺 陷，本文还提出了一种基于度的概率分配算法( d e g r e eb a s e dp r o b a b i l i t ya s s i g n a l g o r i t h m ，d p 从) 。相比于目前的随机分配方法，d p a a 基于真实网络与随机网络的本质特征， 具有较小的抽样偏置。 u e t z 数据集和e c o l i 数据集上的实验结果表明，本文提出的两种模体识别方法能有效 地识别真实生物网络中的模体，相比于目前的方法，具有较小的计算复杂度和较小的抽样偏 置。 关键字 生物网络，模体识别，子图挖掘，抽样 a b s t r a c t i nr e c e n ty e a r s ，a l o n gw i t ht h ed e v e l o p m e n to fb i o t e c h n o l o g y , e s p e c i a l l yi nh i g h t h r o u g h p u t t e c h n o l o g y , b i o l o g i c a ln e t w o r kd a t ah a si n c r e a s e ds i g n i f i c a n t l y t h e r eh a sb e e nal o to fb i o l o g i c a l n e t w o r kd a t a b a s e s ，i n c l u d i n g p r o t e i nr e a c t i o nn e t w o r k s ，m e t a b o l i cn e t w o r k s ，g e n er e g u l a t o r y n e t w o r k sa n dn e u r a ln e t w o r k s h o wt oi d e n t i f yt h es t r u c t u r ew h i c ha s s o c i a t e dw i t ht h eb i o l o g i c a l f u n c t i o n sf r o mt h e s ev a s td a t ai sc u r r e n t l yah o tr e s e a r c ht o p i c ，a n dh o wt of i n dm o t i f sf r o mt h e b i o l o g i c a ln e t w o r ki sak e ys t e pt os t u d yt h es t r u c t u r ea n df u n c t i o no ft h eb i o l o g i c a ln e t w o r k s a m o t i fi sa s u b g r a p ht h a ta p p e a r sm o r eo f t e nt h a ne x p e c t e db yc h a n c e t h em a i ns t r e a mm o t i ff i n d i n ga l g o r i t h m sa r ee n u m e r a t i o na n ds a m p l i n ga tp r e s e n t ，t h ef o r m e r t f yt of i n da l lt h em o t i f si nt h eg i v e nr e a lb i o l o g i c a ln e t w o r k s h o w e v e r , w i t ht h ei n c r e a s i n go ft h e s u b g r a p hs i z e ，t h en u m b e ro fc a n d i d a t es u b g r a p h sg r o w t he x p l o s i v e l y , a n dt h et i m er e q u i r e dt o f i n d i n gm o t i f sg r o w t hr a p i d l y w h i l et h ee x p l o s i v eg r o w t ho fm e m o r ys p a c e ，t h ep r o g r a mw i l l c o l l a p s ed u et om e m o r ye x h a u s t i o n s oe n u m e r a t i o nm e t h o dc a no n l yf i n ds m a l la n d m e d i u m s c a l e m o t i f s t h e r e f o r e ，t h em e t h o do fs a m p l i n gm o t i ff i n d i n gw a sp r o p o s e df o rd e a lw i t ht h ep r o b l e m t h i sm e t h o di g n i f i c a n t l yr e d u c e st h eh i g ht i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y , b yo n l yv i s i t i n g p a r to ft h es u b g r a p hs e t h o w e v e r , t h e r ei ss a m p l i n gb i a sb e c a u s eo ft h ed i f f i c u l t yp r o p o r t i o n a l s a m p l i n g ，a n di tw i l lt a k et h ea d d i t i o n a lc o m p u t a t i o n a lc o m p l e x i t yt oa d j u s tt h eb i a so fr e s u l t i n g m o r e o v e r , i ti sd i f f i c u l tt oa c c u r a t e l ya s s i g nt h ep r o b a b i l i t y f o rt h es a m p l i n gm e t h o d t os o l v et h e s ep r o b l e m s ，t h et r a d i t i o n a lm e t h o d sa r es t u d i e da n de x t e n d e di nt h i sp a p e r an o v e l s u b g r a p hf i n d e ra l g o r i t h mb a s e do np a r t i t i o n ( p s g f ) i sp r o p o s e d ，w h i c hc a ne f f i c i e n t l yf i n da l l s u b g r a p h so ft h es p e c i f i e dr e a lb i o l o g i c a ln e t w o r k s b a s e do nt h ei d e ao fp a r t i t i o n ，p s g fo n l y m a i n t a i nap a t hf r o mt h er o o tn o d et ot h el e a fn o d eo ft h es e a r c ht r e ed u r i n gr u n n i n gp e r i o d ，a n d t h e r e f o r eh a v eas m a l lm e m o r yu s a g e b ya p p l y i n gp s g ft ot h ef r a m e w o r ko ft h em o t i ff i n d i n g ，w e g e n e r a t e dan e we n u m e r a t i o nm o t i ff i n d i n gm e t h o db a s e do np a r t i t i o n ( p n m f ) ，t h i sm e t h o d i d e n t i f i e dm e d i u m - s i z e dm o t i fi nt h eu e t zd a t as e tw i t hl e s st i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y w ea l s op r o p o s e dan o v e lp r o b a b i l i t ya s s i g na l g o r i t h mb a s e do nt h ee s s e n t i a lc h a r a c t e r i s t i c so ft h e r e a lb i o l o g i c a ln e t w o r k s c o m p a r e dw i t ht h eo t h e rs a m p l i n gm e t h o dt h en e wa l g o r i t h mc o u l dg e t t h es m a l l e rs a m p l i n gb i a s e x p e r i m e n t a lr e s u l t so ne c o l id a t as e ta n du e t zd a t as e ts h o wt h a tt h ep r o p o s e dm o t i f f i n d i n gm e t h o d sc a ne f f e c t i v e l y i d e n t i f y m o t i f sf r o mt h er e a lb i o l o g i c a ln e t w o r k sw i t hl e s s c o m p u t a t i o n a lc o m p l e x i t yo rs m a l l e rs a m p l i n gb i a sc o m p a r e d t ot h ec u r r e n tm e t h o d s k e y w o r d s b i o l o g i c a ln e t w o r k s ，m o t i ff i n d i n g ，s u b g r a p hm i n i n g ，s a m p l i n g 目录 摘要i a b s t r a c t ：l l e jj j 匙i i i 第一章绪论1 1 1 研究背景1 1 2 研究现状2 1 3 主要研究内容3 1 4 本文组织结构4 第二章模体识别方法概述5 2 1 生物网络定义及特性5 2 2 模体定义5 2 3 模体识别方法框架6 2 4 模体统计意义7 2 4 1 基丁频率的模体判断7 2 4 2 基于统计的模体判断7 2 5 随机网络模型8 2 6 模体识别方法。1 0 2 6 1 以网络为中心的模体识别方法。1 0 2 6 1 1 穷举法1 2 2 6 1 2 近似算法1 2 2 6 1 3 矩阵计算1 3 2 6 1 4 其他方法1 3 2 6 2 以模体为中心的模体识别方法1 4 2 7 本章小结1 4 第三章基于划分的子图搜索算法1 5 3 1 子图搜索相关方法：一1 5 3 1 1 穷举搜索算法1 5 3 1 2f a n m o d 1 5 3 1 3k a v o s h 1 6 3 2 基于划分的子图搜索算法1 6 3 2 1 基本概念1 6 3 2 2 算法描述1 7 3 5 3 算法分析1 9 3 3 本章小结2 1 第四章基于抽样的模体发现方法。2 2 4 1 基于抽样的模体发现的相关方法2 2 4 1 1m f i n d e r ；2 2 4 1 2f a n m o d 2 2 4 2 基于度的概率分配算法2 3 4 2 1 算法提出背景2 3 4 2 2 实验支持2 4 4 2 2 1 实验一。2 5 - 4 2 2 2 实验二。2 6 4 4 2 3 实验三。2 6 4 2 3 概率分配算法描述。2 7 4 3 本章小结2 9 第五章实验及其分析。3 0 5 1 实验数据3 0 s 2 基于划分的模体识别算法3 0 l 第 致 参 第一章绪论 1 1 研究背景 第一章绪论 近年来，随着生物技术的发展，尤其是高通量技术，出现了很多的生物网络数据。生物 网络是利用网络理论对生物系统进行建模( 系统包含的个体作为顶点，个体间的相互作用作 为边) ，从而借助于网络的概念、属性和复杂网络研究的各种方法来理解生物系统的演化和行 为 5 。从现代生物学知识来看，很多时候更有价值的不是对生物体中的单个分子功能的认识， 而是来自于细胞的大量不同成分( 如蛋白质、d n a 、r n a 和小分子) 之间的交互作用，以及 它们与环境之l h j 的相瓦作用信息。对这种复杂网络的分析和理解已成为2 1 世纪生命科学领 域极具挑战性的研究课题之一。 经常讨论的生物网络有蛋白质作用网络，基因调控网络，新陈代谢网络，神经网络等。 近年来，描述这些网络的数据有了显著的增长，出现了很多生物网络数据库，例如，蛋白质 作用网络数据库有d i p 6 ，i n t a c t 7 ，m i n t 8 ，m p a c t 9 和b i o g r i d 1 0 ，基因调控网络 数据库有r e g u l o n d b 1 1 ，新陈代谢网络数据库有k e g g 1 2 和m e t a c y c 1 3 等。蛋白质作用 网络是生物网络中最重要的一类网络，图1 - 1 所示为酵母菌的蛋白质作用网络 7 2 ，人类的 生命活动依赖于细胞内大量蛋白质之间的相互反应。每一种特定的活动是跟一组特定的蛋白 质反应相关的，即这组特定的蛋白质反应是一个特定的功能模块。所以，研究蛋白质作用网 络可以有助于生物体内的生化过程的理解 1 4 ，有助于新药的研制 1 5 ，有助于生物进化过 程的研究 1 6 等。 图1 - 1 酵母菌蛋白质作用网络 7 2 东南人学硕j ：学位论文 近年来一些研究者对复杂自然网络的全局特性进行了深入研究 3 0 ，例如度分布，网络 直径，聚类系数等，发现这些网络根本就不是随机网络，而是普遍表现出些共同的全局拓 扑特性，例如“小世界 和“无尺度 等。除了全局特性，很多局部特性也被发现，例如m i l o 等人在文献中对一些自然界网络进行了分析 3 0 ，发现存在一些表达程度比随机网络高得多 的子结构，基于“进化过程中会保存特定功能的模块” 5 ，他们称这些重复出现的局部子结 构为模体( m o t i f ) ，模体是一种非常重要的局部特性，网络模体的发现和分析引起了生物信 息学、复杂网络研究和社会统计学等领域的广泛关注 1 7 - 2 3 ，已经成为目前生物信息学的研 究重点和热点之一 1 7 ，1 8 。 模体的识别具有相当重要的意义。m i l o 认为研究过度表达的子结构可以有助于理解生物 网络的设计原则 3 0 。一些研究者已经将模体的识别应用到实际的正e 物湿实验中，并取得了 很好的效果 2 4 2 7 。近年来，一些科学家开始利用模体去分析牛物网络。s a it o 等人利用提 取的模体来检测蛋白质网络( p p i ) 中的误报率 2 4 ，2 5 ；a l b e r t 等人利用模体来预测蛋白质 反应 2 6 ；m i d d e n d o r f 等人利用机器学习方法来对网络进行分类 2 7 。这表明模体可以为复 杂网络的深入研究提供有效的帮助。另一方面，模体与功能的结合是一个很有前景的领域， m i l o 等人在文献中对若干种现实世界的网络进行了分析 3 0 ，发现具有相似功能的网络具有 相同的模体，即模体是功能的载体，功能是模体的表现形式。模体和功能的结合将会为系统 生物学研究带来重大帮助，可以帮助研究生物进化过程中的功能选择 2 8 ，或者定制具有特 定功能的生物网络，这对于药物的发现和丌发具有重要的作用。因此，模体识别是一个非常 重要的研究领域，对于研究生物网络的功能、生物体的进化以及新药研制具有重要的研究意 义和应用价值。 1 2 研究现状 自2 0 0 2 年m i l o 等人在s c i e n c e 上提出网络模体这个概念以来 1 1 ，生物网络中模体识 别技术受到学者的广泛关注，并成为目前生物信息学研究的重点和热点之一。m i l o 在 ( ( s c i e n c e ) ) 上这篇文章截止2 0 1 0 年2 月引用次数已高达1 5 5 0 次。许多国际著名学府及研究 机构，如魏茨曼科学研究所( w e i z m a n ni n s t i t u t eo fs c i e n c e ) 3 0 、哈佛大学 3 4 、麻 省理工学院 3 4 3 、德黑兰大学( u n i v e r s i t yo ft e h r a n ) 3 6 以及新加坡国立大学 3 5 等都 在积极开展生物网络模体识别方法的研究。国内的清华大学、西安电子科技大学、上海大学 和东南大学等也开始对模体发现算法进行了研究。 目前的模体识别方法可以分为以网络为中心的方法 3 0 ，3 1 ，3 2 ，3 3 ，3 5 ，3 6 和以模体为中 心的方法 3 4 3 。第一类方法试图在真实网络中识别指定大小的所有或者大部分模体，典型方 法有穷举法 3 0 ，近似算法 3 1 ，3 2 ，3 3 ，3 5 ，3 7 和矩阵计算方法 3 9 。穷举法开创了模体识别 技术研究的先河 3 0 ，m i l o 等人枚举了一些真实生物网络中指定大小的所有模体，包括基因 调控网络，神经网络，食物链网络，新陈代谢网络等等，识别了一些具有特定功能的模体。 由于真实网络非常复杂，他们仅仅枚举了大小为3 和4 的模体，所以这一类方法效果很不理 想，只能识别小规模的模体。近似算法的典型方法有抽样法 3 1 ，3 2 ，3 3 ，3 7 和n e m o f i n d e r 3 5 ， m f i n d e r 是典型的抽样算法 3 1 ，能够识别的模体大小达到8 ，但最大的缺点是抽样结果存在 抽样偏置，以及修正该偏置而产生的额外计算复杂度，其他的抽样算法还有f a n m o d 3 2 ，3 3 ， 该方法改进了m f i n d e r 的抽样偏置，但具有概率值不易分配的缺点。n e m o f i n d e r 通过对真实 网络进行划分来减小计算量 3 5 ，能够识别中等规模的模体，并且性能有很大提高。矩阵计 算方法是一种很新颖的方法 3 9 ，该方法跟其他方法相比，在效率上具有压倒性的优势，并 且能够用于识别大型模体，但还不成熟，尚需要一些改进。 第二类方法则是在真实网络中查询特定的子图是否为模体，该类方法能够识别的模体大 小有了显著的提高，但只能够查询特定的子图。典型方法为j o s h u a 等人提出的 s y m m e t r y - b r e a k i n g 方法 3 4 ，该方法首先生成查询子图，然后在原图中统计该子图的出现 2 第一章绪论 次数，最后再跟随机图进行比较，计算统计意义。该方法与以网络为中心的方法相比，具有 较低的时间复杂度，能够识别大规模的模体，并且对子图大小具有良好的扩展性，但只能用 于对特定子图的查询。 还有一类基于图的挖掘算法，在图事务中基于a p r i o r i 和d f s 算法挖掘频繁子图 4 3 ， 能够为模体识别技术的研究提供很好的思路，例如a g m 4 4 ，4 5 ，f s g 4 6 ，g s p a n 4 7 ， c l o s e s p a n 4 8 和f f s m 4 9 等。 但是目前对于生物网络中模体识别方法的研究上，存在下面一些问题： 1 由于生物网络的复杂性制约着模体识别方法，目前的穷举模体识别方法只能识别小规 模模体。近似算法虽然可以识别中等规模的模体，但其求解仍具有非常高的计算复杂 度，而且很多近似算法的求解效果存在偏差。对于大规模模体的识别还没有有效的解 决方法。 2 穷举法虽然能够精确识别生物网络中的所有模体，但随着模体大小的增长，时问复杂 度和空间复杂度呈爆炸性增长，所以只能识别小规模的模体。 3 抽样方法能够识别生物网络中的中等规模模体，但只能够部分识别，并且存在抽样偏 置以及修正该偏置所产生的额外计算复杂度。同时，概率的分配也是难点。 1 3 主要研究内容 本文研究的主要内容是针对当前的模体识别方法由于时间复杂度和空i b j 复杂度的限制不 能够识别大规模模体的弱点，研究能够识别大规模模体的模体识别技术。针对当前的抽样模 体识别方法存在抽样偏置，调整该偏置会产生大量额外计算复杂度，以及抽样过程中抽样概 率值难以分配的弱点，利用真实网络和随机网络之间的本质区别，研究一种新的概率分配算 法。该概率分配算法具有较低的抽样误差，最终利用该算法在真实网络中识别大规模模体。 下面将本文研究内容概述如下： 基于划分的思想实现了一种高效的穷举模体识别算法随着子图顶点个数的增长，真 实网络中候选子图的数量呈爆炸性增长，要想识别出给定大小的所有子图，在时间复 杂度和空间复杂度上受到极大的挑战，迫切需要一种不重复，不遗漏，高效的子图搜 索算法。基于划分的思想本文提出了一种高效的子图搜索算法，所有子图的搜索过程 就是若干棵搜索树的产生过程，搜索树的叶结点即为要识别的目标子图。不同的搜索 树之间通过全局划分顶点来实现子图的不重复识别，搜索树内部通过局部划分顶点来 实现子图的不重复识别；在搜索树的某个结点产生子结点时，通过加入该结点中的顶 点的所有邻接顶点来进行扩展，从而可以不遗漏任何子图；由于不重复，不遗漏任何 子图，所有子图一旦被识别，即可从内存释放，所以时间复杂度和空间复杂度也很理 想。 研究利用真实网络和随机网络之间的本质区别，实现了一种概率分配算法由于穷举 模体识别方法对整个子图空间进行穷举遍历，随着子图顶点个数的增长，时间复杂度 和空间复杂度急剧增长。在这样的背景下产生了抽样算法，抽样算法部分访问子图空 间，解决了穷举模体识别技术时间复杂度和空间复杂度过大的问题，但也引入了一些 新问题：抽样概率难以精确分配，从而产生抽样偏置，以及调整该偏置而引入的额外 计算复杂度。本文首次提出了一种精确的概率分配算法，这种概率分配算法产生较小 的抽样偏置。由于目前的模体识别方法都是将真实网络中子图的出现情况去跟随机网 络中子图的出现情况做比较，所以基于真实网络和随机网络之间的本质区别来进行概 率分配更能体现真实网络的固有特征。真实网络和随机网络最本质的区别之一是真实 网络具有一些度非常高的顶点，而随机网络顶点的度则非常平均。基于这点提出了一 种概率分配算法，并且在两个数据集上证明了这种抽样算法具有较小的抽样偏置，从 而能够更精确的抽样识别真实网络的模体。同时，本文还将该概率分配算法与前述的 3 东南人学硕一i ：学位论文 基于划分的子图搜索算法相结合，实现了一种抽样模体识别方法，在u e t z 数据集上 识别了大小为1 4 的大规模模体。 1 4 本文组织结构 本文共分为六章，内容安排如下： 第一章，阐述了本文研究对象的相关背景知识，包括课题的研究背景、国内外目前的研 究现状、本文的研究内容以及本文的组织结构。 第二章，介绍本文涉及的一些关键技术及模体识别算法的整体框架，并且介绍了目前的 一些典型的模体识别算法。 第三章，详细介绍了基于划分的子图搜索算法。首先介绍了目前的三种子图搜索算法， 并讨论了他们的优缺点，最后详细介绍了一种基于划分的子图搜索算法，通过一个例子详细 地介绍了该算法的整个运行过程，并且证明了该算法的正确性。 第四章，详细介绍了基于抽样的模体识别算法。首先介绍了一种基于真实网络与随机网 络本质区别的概率分配算法，最后介绍了一种抽样模体识别算法。 第五章，系统地介绍了本文的模型结构，并对其在e c o l i 和u e t z 数据集上的实验进 行了分析，且与其他在这两个数掘集上做过实验的算法的结果进行了比较分析。 第六章，本文的总结，并指出了有待改进的研究工作。 4 第二章模体识别方泫概述 第二章模体识别方法概述 在第一章中介绍了模体识别方法的研究背景以及国内外的研究现状，本章将介绍模体识 别中涉及到的一些相关概念和相关技术，主要是生物网络的定义，模体的定义、特性及统计 方法，以及模体识别方法的整体框架和一些典型模体识别方法。 2 1 生物网络定义及特性 生物网络可以用图来表示，反应物表示为图的顶点，反应物之间的关系表示为图的边。 不妨假设该图为g ，g 是由顶点集合y 和边集合e 组成，记为g = ，e ) 。其中v ( o ) 是顶点 的有限集合，且v 乒g ；e ( g ) 是边的有限集合，边由y 中的不同顶点对构成。生物网络可以 分为有向图和无向图，例如新陈代谢网络，基因调控网络以及神经网络等都是用有向图来表 示，而蛋白质作用网络则是用无向图来表示。 下面介绍一下模体识别过程中涉及到的一些图的概念和特性： 定义l ：诱导子图。设g ：，e ) 和g 。= ( k ，e 。) 为两个图，若k v 且e 。e ，则称g ，是 g 的子图。若e 。是由两个端点都在k 中的边组成，则称g 。是g 的诱导子图。在本文中提到 的子图大小，如没有特殊说明，都是指顶点个数。 图g = ，e ) 的邻接矩阵a 是一个n * r t 的二维数组，当且仅当( i ，_ ) ( 或 ) 是e ( g ) 中的一条边时，彳p 1 【，1 = 1 ，否则彳【f 1 【1 = 0 。 定义2 ：同构。设g 1 = 似，巨) 和g 2 = 似，e ：) 为两个图，若存在映射函数厂：k 呻k ，对 于q ，v k ，“，1 ，f ) e ，当且仅当厂( u ) ，f ( v f ) k ，( ，( v i ) ，厂( v ) ) e ：，则称g 1 ，g 2 同构 5 0 。 也就是说，若两个图同构，则顶点与顶点之间，边与边之间都存在一一对应关系，而且 它们的关联关系也必须保持相应的一一对应关系。判断两个图是否同构是一个介于n p 和n p c 之间问题 5 1 ，有待进一步研究，尚没有有效算法来解决。在模体识别方法中，图同构测试 是一个必不可少的中间过程，所以图同构测试的复杂性制约着模体识别方法。 2 2 模体定义 模体是指在某个网络的多个不同部分出现的某一相互连接的子结构，其表达程度明显高 于在随机网络中的表达 2 9 ，由s h e n ，m il o 等人中首次提出 2 9 。图2 1 为酵母菌网络中的 模体示意图 7 3 ，该网络为蛋白质反应网络和基因调控网络的混合网络，其中虚线表示蛋白 质反应网络中的边，细实线表示基因调控网络中的边，粗实线则表示两种网络中都存在的边， 阴影部分所示为模体。 5 东南人学硕l ：学位论文 2 3 模体识别方法框架 图2 - 1 酵母菌网络中的模体 7 3 】 c 函 瓣 一个典型的模体识别方法由三步构成：第一步，在原图中找出特定大小的所有子图及其 出现次数；第二步，分析第一步中的所有子图，将同构的子图归为同一类，并且将他们的出 现次数相加，作为该类子图的总出现次数；第三步，将这些子图类在原图中出现的频率与在 一组随机图中出现的频率作比较，计算统计意义，判断是否是模体。整个模体识别方法框架 由图2 - 2 所示： 6 2 4 模体统计意义 模体有两种判断方式，分别基于频率和统计意义。前者认为模体是在原图中表达次数超 过某个阀值的子图，后者认为模体是表达程度在原图中高于在一系列随机图中的子图。这两 种判断方式是不等价的，即用某种方式判断的模体不一定会被另一种方式认可。文献 3 0 认 为上述的两种模体判断方式有个缺点，可能会遗漏那些功能上很重要，但是在统计上没有意 义的模体，即统计上有意义的模体不一定在功能上也是重要的。 2 4 1 基于频率的模体判断 子图的频率与计算子图出现次数时采取的重叠策略相关。文献中提出了计算子图频率时 的三种重叠策略 4 1 1 ，分别用e ，e ，只表示。e 允许任意顶点和边的重叠，最只允许顶点的 重叠，即边不相交性，e 不允许顶点和边的重叠，即同时满足边不相交性和顶点不相交性。 向下封闭性是频率的一个很有用的性质，是指子图的频率随着子图增大单调递减，即模体识 别过程中，如果某个子图表达次数低于某个阀值，则所有由该子图扩展而得到的子图都会低 于这个阀值。该性质极大的缩小了候选子图的数量，使得可以使用a p r i o r i 算法对子图进行 剪枝 4 3 。上述的三种重叠策略中，e ，只保持向下封闭性，而e 则不保持。因此在设计模 体搜索算法时如何计算子图频率是一个很关键的问题。在文献 2 9 ，3 0 ，3 1 ，3 5 ，4 0 ，5 4 ，5 5 ，5 6 ，5 7 ，5 8 中提出的方法，都是使用了允许任意重叠的频率定义。在 蛋白质反应网络中，同一种蛋白质经常在若干个模块中分别承担不同的作用，因此允许子图 任意顶点和边的重叠是合理的。在本文中也采用了允许任意重叠的策略。 文献 5 9 中提出了模体的一个重要性质极大性。如果一个模体g 不被任何其他模体 包含，则这个模体是极大的。极大性的优点是可以显著缩略最终的结果集合，并且没有任何 信息损失，因为任何小模体都可以从极大模体导出。 2 4 2 基于统计的模体判断 在前一节中介绍了基于频率的模体判断方式，现在介绍基于缄卜意义的模体判断方式。 根据模体的定义，模体是过度表达的子结构，也就是说模体是在原网络中出现比例明显高于 7 奎塑叁兰堡：! = 堂篁笙奎 在同一网络的完全随机化形式中出现的比例。目前的统计方法有z s c o r e 3 0 ， p v a l u e 3 3 ，6 0 ，a 法 5 5 和阀值法 3 5 ，分别介绍如下： z s c o r e 于文献 3 0 中提出，如式( 1 ) 所示： z ( g 。) ；血亟匕幽 ( 1 ) 、“ s t d ( 厶耐( q ” 其中厶，( g ) 是子图q 在真实网络中的出现次数，f r o , ( g ) 和s t d ( l 耐( 瓯) ) 分别是子图g 在 一系列随机网络中出现次数的平均值和标准差。如果子图是过度表达的，z s c o r e 就会很大， 反之，z s c o r e 就会是负数，或者接近于零。文献 6 0 中提出，如果z s c o r e 值大于l ，则 认为该子图是过分表达的。 在文献 5 5 中介绍了真实网络的一个有趣特征一s p ( s i g n i f i c a n c ep r o f i l e ) 。s p 是一个 向量，表示该网络的子图集合的z s c o r e 值。该子图集合一般为某个特定大小的所有子图， s p 被规格化为长度为l ，这样z s c o r e 值为负数，尤其是接近于一1 的项，说明相应的子图的 表达水平很低，那些z s c o r e 接近1 的子图则会被识别为模体，s p 也可以用于不同网络之间 的比较。 p v a l u e 于文献 3 3 ，6 0 中提出，如式( 2 ) 所示： 1 卫 p ( g ) 2 言乏6 ”吣帕) ( 2 ) 其中( q ) 是子图q 在真实网络中出现的频率，而( q ) 是子图q 在随机网络中出现的频率， 是随机网络的个数。当条件c 成立时，6 ，为1 ，否则为o 。p v a l u e 值越小，子图q 越可能 是模体。如果p v a l u e 值小于0 0 1 ，则认为该子图是过分表达的 3 0 。为了合理的计算 p v a l u e ，一般至少需要考虑一千个随机网络，然而如果考虑的随机网络比较少，则可以使 用z s c o r e 法。 法于文献 5 5 中提出，如式( 3 ) 所示： ( g 。) ；丛丛三盟 ( 3 ) 、“厶，( q ) + ，删( g ) + 其中丸，( q ) 是子图g 在真实网络中的出现次数，厂删( g ) 是子图q 在一系列随机网络中 出现次数的平均值，是一个很小的常量，当子图在真实网络和随机网路中出现次数很少时， 可以防止变化太大。的取值范围介于一l 和1 之间，1 表示子图是过度表达的。尽管在 生物文献中很少使用，实际上比z s c o r e 更加具有实际意义。 阀值法就是直接定义一个阀值，文献 3 5 定义模体为r e p e a t e d 和u n i q u e 的子图。r e p e a t e d 是指子图在原图中出现的次数超过了某个用户自定义的阀值t ，u n i q u e 则是指在一系列n 个 随机网络中，子图至少在t 。个网络中出现超过f r 次，这里，气和n 均为给定的参数，乙即为 直接定义的阀值。 2 5 随机网络模型 模体定义为实际网络中表达程度显著高于随机网络中的表达的子图。为了计算子图的统 计意义，本文将子图在现实网络中的表达与在一系列随机网络中的表达进行比较。由于这些 随机网络不具有局部结构，称之为空模型网络( n u l lm o d e l ) 6 1 】。然而，如何选择随机网络模型 以及如何生成这些随机网络呢? 文献【6 1 1 简单介绍了在复杂网络分析中涉及的一些典型性质和概念，例如距离，平均路 径长度，聚类系数，度分布，相关系数等，这些性质描述了复杂网络的拓扑结构。 平均路径长度描述了网络中顶点之间的分离程度，很多现实网络具有海量的顶点，但其 8 第二苹模体识别方法4 c 述 平均路径长度却非常小，例如，文献 6 2 x , j 新陈代谢网络进行了分析，其平均路径长度仅仅 为3 ，这就解释了很多现实网络都具有“小世界”的全局拓扑特性，小世界网络起源于社会 学家的“六度分离”理论。 聚类系数描述了网络的局部聚结程度。很多现实