（交通信息工程及控制专业论文）频繁子图挖掘算法及其在生物网络中的应用.pdf

摘要 人类基因组计划的基本完成表明后基因组时代的到来。人类积累的大量的生物信息数据 为揭开生命奥秘提供了数据基础，生物学研究的热点由对细胞内个别基因或蛋白质功能的局 部性研究，转移到以细胞内全部的基因、蛋白质及代谢产物为整体对象的系统研究。对基因 调控网络、蛋白质相互作用网络、代谢路径网络等结构及功能模块的检测技术的研究，逐步 把分子生物学推入系统生物学时代。基因与蛋白质通过网状的相互作用产生更高一级的功能 模块，所以，通过数学建模来设计有效的算法，在生物网络中进行功能模块的挖掘和分析， 将有助于更好地研究生物体自身的功能和不同生物体之间的进化关系，为分析理解生命基本 规律提供依据。 本文对基于图论的经典频繁子图挖掘算法进行了系统的研究和全面的总结，在此基础上 提出了一种新的挖掘频繁子图的算法，该算法包含子图的搜索算法及同构分类算法。对子图 搜索问题，提出了环分布的概念，并构造了基于环分布的子图搜索算法e s r ( e n u m e r a t e s u b g r a p h sb a s e d o nr i n g ) ；对子图同构问题，利用度序列和特征值构造了两种算法，分别用于 对有向图和无向图的同构判别；利用同构算法对搜索出的子图进行同构分类，根据分类结果 得到频繁子图。当网络规模比较大时，子图数量非常庞大，同构分类的工作量很大，为此又 提出了随机归类算法和h a m i l t o n 子图的挖掘算法，以减少同构分类的运算量。随机归类算法 是通过从子图集中随机地抽取一定数量的子图进行同构分类，是一种近似的算法；h a m i l t o n 子图的挖掘算法旨在挖掘特定类型( 具有h a m i l t o n 回路) 的子图，以减少搜索结果集。最后 对5 个真实生物网络进行了仿真实验研究，找出了不同规模的频繁子图，实验结果表明本文 提出的算法优于现有的算法。 关键词：数据挖掘，频繁子图，同构，模体，算法，h a m i l t o n 子图 a b s t r a c t t h em a j o rc o m p l e t i o no fh u m a ng e n o m ep l a ni n d i c a t et h a tt h ea g eo fp o s t g e n o m ei sf i n a l l y c o m i n g t h ea b u n d a n tb i o i n f o r m a t i o nd a t ap e o p l ea c c u m u l a t e di nr e c e n ty e a r sp r o v i d et h eb a s i c r e f e r e n c ef o rr e v e a l i n gt h em y s t e r yo fl i v e s ，a n dt h ef o c u so fr e s e a r c hi nb i o l o g yh a v ec h a n g e df r o m t h ep a r t i a lr e s e a r c ho fi n d i v i d u a lg e n e so rp r o t e i n si nc e l l st ot h es y s t e mr e s e a r c hb a s e do nt h e e n t i r eg e n e sa n dp r o t e i n sa sw e l la st h em e t a b o l i cp r o d u c t s t h er e s e a r c ho nt h es t r u c t u r ea n dt h e d e t e c t i o nt e c h n i q u eo ng e n er e g u l a t o r yn e t w o r k s ，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 sa n d m e t a b o l i cn e t w o r k sh a v ep r o m o t e dt h em o l e c u l e - b i o l o g ya g et ot h es y s t e m - b i o l o g ya g es t a g eb y s t a g e g e n e sa n dp r o t e i n s c a ng e n e r a t es u p e r i o r i t yf u n c t i o n a lm o d u l e sb yn e t t yi n t e r a c t i o n s ， t h e r e f o r e ，u s i n gm a t h e m a t i cm o d e l i n gt od e s i g ne f f i c i e n ta l g o r i t h m sf o rm i n i n ga n da n a l y z i n gt h e m o d u l e si sh e l pt os t u d yt h ef u n c t i o n so ft h eo r g a n i s mi t s e l fa n dt h ee v o l v e m e n tr e l a t i o n sb e t w e e n d i f f e r e n ts p e c i e s ，a n dc o u l dp r o v i d ew a r r a n t sf o ra n a l y z i n ga n du n d e r s t a n d i n gt h eb a s i cd i s c i p l i n e s o fl i v e s i nt h i sp a p e r , s o m ew o r k sa r ed o n ei nt h ef r e q u e n ts u b g r a p hm i n i n g s o m ec l a s s i c a lg r a p h b a s e da l g o r i t h m sf o rm i n i n gf r e q u e n ts u b g r a p h sa r es y s t e m a t i c a l l y s t u d i e da n dc o m p r e h e n s i v e l ys u m m a r i z e di nt h i sp a p e r b a s e do nt h i s ，an o v e la l g o r i t h mf o rm i n i n g f r e q u e n ts u b g r a p h si sp r o p o s e d ，w h i c hc o n s i s t so fs u b g r a p hs e a r c h i n ga n dg r a p hi s o m o r p h i s m t e s t i n g f o rs u b g r a p hs e a r c h i n g ，ad e f i n i t i o no fr i n gd e s t r i b u t i o ni si n t r o d u c e d ，a n da na l g o r i t h m b a s e do nr i n gd i s t r i b u t i o n e s r ( e n u m e r a t es u b g r a p h sb a s e do nr i n g ) i sp r e s e n t e d f o rg r a p h i s o m o r p h i s m ，b yu s i n gd e g r e es e q u e n c e sa n de i g e n v a l u e so fag r a p h ，t w oa l g o r i t h m sa r ep r o p o s e d f o rd i r e c t e dg r a p h sa n du n d i r e c t e do n e s ，r e s p e c t i v e l y g r a p hi s o m o r p h i s ma l g o r i t h mi su s e dt o c a t e g o r i z et h es e a r c h e ds u b g r a p h s ，a n df r e q u e n ts u b g r a p h sa r eo b t a i n e da c c o r d i n gt ot h er e s u l to f t h ec a t e g o r i z i n g w h e nt h es i z eo fan e t w o r ki sl a r g e ，t h e r ea r eal a r g en u m b e ro fs u b g r a p h s ，w h i c h l e a d st oh i 曲c o m p u t a t i o n a le f f o r t a sar e s u l t ，w ep u tf o r w a r dar a n d o mc a t e g o r i z i n ga l g o r i t ma n d ah a m i l t o ns u b g r a p hm i n i n ga l g o r i t h m t h ef o r m e rs e l e c t sa tr a n d o mac e r t a i nq u a n t i t yo f s u b g r a p h sf o ri s o m o r p h i s mt e s t i n g ，w h i c hi s a na p p r o x i m a t ea l g o r i t h m a n dt h el a t t e ra i m sa t f i n d i n go n l yc e r t a i nt y p eo fs u b g r a p h s ，s u c ha ss u b g r a p h sw i t hh a m i l t o nc y c l e ，w h i c hr e d u c e st h e n u m b e ro fs e a r c h e ds u b g r a p h s e x p e r i m e n t a le v a l u a t i o no nf i v er e a lb i o l o g i c a ln e t w o r k ss h o w st h a t o u ra l g o r i t h mi ss u p e r i o rt ot h ea l g o r i t h m sa v a i l a b l e k e y w o r d s ：d a t am i n i n g ，f r e q u e n ts u b g r a p h ，g r a p hi s o m o r p h i s m ，m o t i f , a l g o r i t h m ，h a m i l t o n s u b g r a p h i i 论文独创性声明 、本人声明：本人所呈交的学位论文是在导师的指导下，独立进行 研究工作所取得的成果。除论文中已经注明引用韵内容外，对论文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论 文中不包含任何未加明确注明的其他个人或集体已经公开发表的成 田 木0 本声明的法律责任由本人承担。 论文作者签名： 毒鼬秘 论文知识产权权属声明 巧年垆胧日 本人在导师指导下所完成的论文及相关的职务作品，知识产权归 属学校。学校享有以任何方式发表、复制、公开阅览、借阅以及申请 专利等权利。本人离校后发表或使用学位论文或与该论文直接相关的 学术论文或成果时，署名单位仍然为长安大学。 ( 保密的论文在解密后应遵守此规定) 论文作者签名： 导师签名： 荔终日 易永峰 一年媚似日 叩年午影日 长安大学硕士学位论文 第一章绪论 1 1 研究背景 2 0 世纪8 0 年代末随着人类基因组计j l j ( h u m a ng e n o m ep r o j e c t ，h g p ) 的启动，生物信息学 迅速兴起；生物学研究的热点由对细胞内个别基因或蛋白质功能的局部性研究，转移到以细 胞内全部的基因、蛋白质及代谢产物为整体对象的系统研究。对基因调控网络、蛋白质相互 作用网络、代谢路径网络等结构及功能模块的检测技术的研究，逐步把分子生物学推入系统 生物学时代，同时也把生物信息学带入了后基因组信息学时代。 近年来，生命科学研究【2 】取得了突破性的进展，人类基因组计划也基本完成，积累了大量 的生物信息数据，为揭开生命奥秘提供了数据基础。现代生物学研究方法也伴随着基因组研 究、信息技术的发展及其在生物研究中越来越广泛深入的应用而发生了深刻的变化。从生物 学、细胞生物学到分子生物学，现代生物研究更多地依赖于信息技术的分析结果来提供进一 步研究的线索和依据，强有力的数据处理分析工具成为现代生物科学研究发展的关键。生物 信息或基因数据挖掘【3 】和通常的数据挖掘相比，生物信息或基因的数据挖掘在数据的复杂程 度、数据量以及分析和建立模型的算法等方面都要复杂得多。在这个过程中，需要对实验数 据进行处理和理论分析，在此基础上解释实验现象，认识实验现象发生的本质，探索固有的 生物学规律，进而了解和掌握生命的物质基础和生命的本质。随着生物科学和技术的迅速发 展，生物数据积累速度不断加快，因此也就对生物数据的科学分析方法和实用分析工具提出 了更新、更高的要求，生物信息学这门交叉学科迅速发展并受到越来越多的重视。 目前生物信息学的主要任务是研究生物分子数据的获取、存储和查询，发展数据分析方法， 主要包括三个方面内容：第一是收集和管理生物分子数据。生物分子数据来自于生物学实验， 应用信息学技术搜集和管理这些数据，将各种数据以一定的表示形式存放在计算机中，建立 数据库系统，并提供数据查询和数据通讯工具；第二是进行数据处理和分析。通过信息分析， 发现数据之间的关系，发现本质规律，进而上升为生物学知识。随着生物技术特别是分子生 物学技术的发展，人们目前己经积累了大量的生物信息学数据，尤其是国际分子生物学的三 大核心数据库一g e n b a n k 核酸序列数据库、s w i s s p r o t 蛋白质序列数据库和p d b 生物大分 子结构数据库【9 1 ，围绕这三大核心数据库还有众多面向各种特定应用的衍生数据库和分析软 件，这些数据库分别从不同角度、以不同方式对各类生物信息学数据进行归纳、总结和注释， 而各种分析软件则为挖掘这些数据提供了有力的工具；第三是开发分析工具和实用软件，解 决具体的问题，为具体的生物信息学应用服务。如生物分子序列比较工具、基因识别工具、 生物分子结构预测工具、基因表达数据分析工具等。 国外一直非常重视生物信息学的发展，各种专业研究机构以及公司的数量与日俱增。目前 国外许多大学和研究机构也已经各自成立了自己的生物信息学部门或中心。就专业机构的角 度来讲，美国于1 9 8 8 年在国会的支持下成立了国家生物信息中心( n c b i ) ，欧洲于1 9 9 3 年3 第一章绪论 月就着手建立欧洲生物信息学研究所( e b i ) ，日本也于1 9 9 5 年4 月建立了自己的生物信息学 中一l , ( c i b ) 。这三个专业机构共同的目的是进行计算分子生物基础研究，构建和发布分子生物 学数据库。 国内对生物信息学领域也越来越重视。在一些著名院士和教授的带领下，在各自领域取得 了一定的成绩，有的在国际上还占有一席之地，如北京大学在生物信息学网站建设方面，中 科院生物物理所在e s t 序列拼接研究方面，天津大学在d n a 序列的几何分析【8 】方面，都有 了新的达到国际最先进水平的研究成果。国内如中科院理论物理研究所、清华大学、复旦大 学、东南大学等等都开展了生物信息学的相关课题，并成立了专门的生物信息学研究机构。 其中北京大学于1 9 9 7 年3 月成立了生物信息学中心，中科院上海生命科学研究院也于2 0 0 0 年3 月成立了生物信息中心，这两个机构分别维护着国内两个专业水平相对较高的生物信息 学网站。复旦大学数据挖掘讨论组对生物信息学中的数据挖掘技术进行了探讨，并开设了相 关课题。但从国内总体水平上来看，与国际水平还有一定的差距。 1 2 研究现状 对多种分子和基因相互作用网络( 基因调控网络、蛋白相互作用网络、代谢网络等) 的研究 来分析生物功能，其核心问题就发现网络的功能模块，其目的是了解生物系统如何在基本单 元的基础上组织起来，并产生一定的生物功能，为分析理解生命基本规律提供依据。近期研 究表吲卜3 1 ，模体是复杂网络的基本模块，生物网络模体的挖掘包括2 个主要步骤：1 频繁子 图挖掘，它包括子图搜索和同构分类两个问题；2 产生对应的随机网络图，比较真实网络和 随机网络，从而去发现生物网络中基本功能模块单元一模体。 频繁子图挖掘过程中涉及到的两个问题都是n p 完全问题，近年来，关于频繁子图挖掘算 法的研究很受关注。1 9 9 4 年l b h o l d e r 等人【4 j 提出了著名的子图挖掘算法s u b d u e ，该算法利 用启发式的搜索策略挖掘频繁子图，但不能完全保证结果集的完整性。算法使用了模糊计算 的方法，提高了挖掘效率，但主要是针对生物应用领域中的特殊问题。1 9 9 4 年，k y o s h i d a 等人【5 】提出了一个子图挖掘算法g b i ，类似于s u b d u e 算法，但采用了不同的启发式搜索策略。 1 9 9 8 年，l d e h a s p e 等人【6 】同样提出了在生物化合物分子库中挖掘频繁子图的算法。2 0 0 0 年， a i n o k u c h i 等人【7 j 提出了一个基于a p f i o f i 思想的频繁子图挖掘算法a g m 。该算法不同于以往 的近似算法，它是挖掘频繁子图完全集的。随后在a g m 算法的基础上，提出了挖掘连通频繁 子图的算法a c g m t 引。2 0 0 1 年，m k u r a m o c h i 等人【9 】提出了一个频繁子图挖掘算法f s g ，同样 采用了a p f i o r i 思想，但不同之处在于通过增量方式逐层挖掘频繁子图，在算法性能上，f s g 优于a c g m ；2 0 0 5 年，他们【1 0 又提出了一个新的子图挖掘问题，即在1 个稀疏的超大规模的图 中挖掘不相邻的子图模式，针对此问题给出了2 个算法h s i g r a m 和v s i g r a m ，分别采用宽 度优先遍历和深度优先遍历的方法挖掘子图。2 0 0 2 年，出现了几种不同的频繁子图挖掘算法 1 1 , 1 2 , 1 3 , 1 4 】，期间重要的成果是x y a n 等人1 4 】提出了一个新颖的深度优先搜索图空间的方法， 2 长安大学硕士学位论文 并在此基础上给出了频繁子图挖掘算法g s p a n 。g s p a n 算法与a c g m 算法、f s g 算法不同，它 没有采用a p f i o f i 思, 想，而是利用边模式增长的方式深度优先挖掘频繁子图；2 0 0 3 年，他们【l 5 】 在g s p a n 算法的基础上，进一步提出了挖掘频繁闭合子图的算法c l o s e g r a p h ，频繁闭合子图集 是频繁子图集的压缩表达方式。2 0 0 3 年，j h u a n 等人【16 】提出了一个新的子图扩展策略，在此 基础上形成了频繁子图挖掘算法f f s m ；其后对f f s m 算法进行改进，得到最大频繁子图挖掘 算、法s p i n t l7 1 。2 0 0 4 年之后，s w e m i c k e 等在这一领域做了大量的研究工伊1 8 ，19 1 。除了上述这 些通用的图模式挖掘算法外，研究人员还提出了一些针对实际问题的图模式挖掘算法【2 0 , 2 1 , 2 2 。 综上所述，虽然基于频繁子图挖掘算法的研究较多，但由于问题本身的复杂度及其特殊的应 用领域导致现有算法的效率不尽如人意，针对算法的实验基本上只做了7 个节点以下的频繁子 图的挖掘。 随机网络作为二个参照标准，通过它可以从真实网络的频繁子图中过滤出模体，所以它的 合理性直接影响到模体的精确性。目前关于随机网络产生的模型主要：1 完全随即网络( e r 模型) 1 2 3 】，它是以完全相同的概率p 给每一对节点连上边，其度分布可用泊松分布来描述； 2 小世界模型( s w 模型) 2 4 ，其算法是先产生一个具有n 个节点的最近邻耦合网络，再进 行随机化重连，但它有可能破坏网络的连通性，从而提出了n w 小世界模型；3 无标度网络 模型( b a 模型) 【2 5 1 ，该模型是通过节点增长，优先连接( 根据已有节点的度确定新增节点 和已有节点的连接概率p ，) ；4 适应度模型【26 | ，它的算法思想类似b a 模型，在确定连接概 率p 。时，引入了适应度分布函数，比b a 模型更具有一般性。此外还有局域世界演化网络模 型等。每一种随机网络模型都有一定的特征，在生物网络模体发现问题中如何选择( 或建立) 随机网络模型，需要分析生物网络的产生机制。 国内关于这一领域的研究文献还不是很多，颜跃进【27 】提出了一种新的深度优先搜索最大 频繁项集的算法；汪卫 2 8 选择了惟一标号图进行分析，结合图论和频集生成的算法，提出了 基于a p r o i f i 思想、运用矩阵乘法的a m g m 算法和基于s f p 树的s f p 算法。 总之，模体挖掘算法的研究深受关注，研究成果也很多，但还两个突出的问题：1 、现有 算法的效率还有待提高，以便挖掘更大( 节点数多) 的模体。2 、在随机网络模型的选择甚至 构造上还有待于进一步的研究，确保模体的精确性。 ，1 3 研究的意义和目的 1 3 1 研究的意义 人类基因组计划的基本完成表明后基因组时代的到来生物学研究的热点由对细胞内个 别基因或蛋白质功能的局部性研究，转移到以细胞内全部的基因，m r n a ，蛋白质及代谢产物 为研究对象的各种“组学”研究，即整体性研究基因组学、转录组学、蛋白质组学、代谢组学 等各种组学技术，逐步把分子生物学推入系统生物学时代，同时也把生物信息学带入了后基 因组信息学时代由于基因与蛋白质倾向于成组地通过网状的相互作用而影响生物系统的功 第一章绪论 能，因此对功能的研究必须分析其相互作用的网络后基因组信息学是通过对多种分子和基 因相互作用网络( 基因调控网络、信号转导网络、蛋白相互作用网络、代谢网络等) 的研究来 进行生物功能的分析，目标是理解生物系统如何在单个构造模块的基础上组织起来，是对包 括从基因组信息到对生命基本规律理解的一系列生物学知识的综合，同时它也有在生物化学 领域应用的实际目的1 2 9 1 代谢处于生命活动调控的末端，是驱动生命过程的化学引擎，产生能量来驱动各种细胞过 程，降解和合成许多不同的分子代谢网络把细胞内所有生化反应表示为一个网络，反映了 所有参与代谢过程的化合物之间以及所有催化酶之间的相互作用，是对细胞代谢的抽象表达 研究代谢网络能帮助我们更好地认识和利用细胞代谢过程。从而促进发酵工程、制药工业等 产业的发展另一方面，网络的拓扑结构是网络形成和进化的反映，研究代谢网络的结构特 征，能帮助我们认识代谢网络的形成演化机理，从而更好地理解生命进化过程 1 3 2 研究的目标 基因与蛋白质通过网状的相互作用产生更高一级的功能模块，对多种分子和基因相互作用 网络( 基因调控网络、蛋白相互作用网络、代谢网络等) 的研究来分析生物功能，其核心问题 就发现网络的功能模块，其目的是了解生物系统如何在基本单元的基础上组织起来，并产生 一定的生物功能，将有助于更好地研究生物体自身的功能和不同生物体之间的进化关系生， 为分析理解生命基本规律提供依据。 近期研究表明，模体是复杂网络的基本功能模块，网络模体挖掘包括3 个主要的步骤：首 先在大的网络中搜索出所有固定大小的子图( k 个节点) ；然后比较这些子图，看它们是否同 构( 结构完全一样) ，将同构的子图分成一类，统计各类子图的频率；最后，产生一个对应的 随机网络，并统计出各类子图的频率，比较这两个网络的子图频率，相对随机网络频率较高 的子图即为模体，它代表真实网络中的功能模块。论文研究的具体目标是： 1 改进现有的子图搜索算法，通过网络的连接矩阵，利用代数方法构造高效的子图搜索 算法，从根本上提高模体挖掘的效率。 2 当子图数量很大时，同构比较的时间代价很高；子图同构的本质是矩阵相似性问题， 我们将利用矩阵特征值理论，设计高效的子图同构算法，进一步提高模体挖掘的效率。 3 考虑到前两步的任务是统计子图频率， 机抽样来估计子图频率，并对误差进行估计； 的时间和空间效率。 我们将利用统计原理( 中心极限定理) ，通过随 这样可以最大程度的提高子图搜索和同构分类 4 在一定的条件下，或者针对某种特定的网络，所要挖掘的模体可能是具有h a m i l t o n 回 路结构，基于这一设想，提出了h a m i l t o n 子图的有效挖掘算法。 5 随机网络作为一个参照体系，它的合理性直接影响挖掘结果的精确性，我们将利用统 4 长安大学硕士学位论文 计理论并结合生物网络的产生机制研究并确定合理的随机网络模型。 6 利用真实网络进行仿真实验。 1 4 研究内容 本文以下各章节的基本内容组织如下： 第二章：生物网络的图论模型，主要包括生物网络模型介绍，图论概念，随机网络，生物 数据的图论描述等，为下一章的讨论做准备。 第三章：频繁子图挖掘算法，首先介绍已有的算法，然后详细描述本文提出的算法，本文 算法包括三个主要内容：1 、基于环分布的子图搜索算法，2 、基于矩阵特征值理论的子图同 构算法，3 、基于统计理论的子图频率计算。 第四章：h a m i l t o n 子图的有效挖掘算法。 第五章：实验结果及分析。 第六章：总结与展望。 第二章生物网络的圈论模型 第二章生物网络的图论模型 21 生物网络 由于生物体的复杂性，通常将研究对象分为三种网络：代谢网络，蛋白质作用网络和调 控网络。这三种生物网络并不是独立的，而是相互重叠，相互作用影响的。其中最适合研究 的是调控网络。代谢网络最为基础，也就最保守。这些数据保存在生物网络数据库中，比较 有影响的数据库主要有启动子数据库s c d p ( 旦亚：g ；g 盟a 丛：q 醒， h t t p j i n c y t e c o m c o r t t r o l r e s c a r c h p r o d u c t s i a s i l i e o p r o t c o m e ) ，d i p ( d a t a b a s eo f i n t e r a c t i n g p z o t e i n ， h t t p ：d i pd o e - m b iu c l ae d u ) 数据库，y - e g g ( k y o t oe n c y c l o p e d i ao f g e n e sa n dg e n o m e s ) 数据 库。 2 1 1 基因调控网络 一组调控因子如何调控一套基因表达的过程称为基因表达调控网络。基因表达调控网络 是基因调控网络的一个重要部分。参与基因表达调控网络的元素主要包括c d n a 、m r n a 、 蛋白、小分子等。从元素阳j 相互联系的角度来看，基因表达调控网络是一个由节点( 调控元 素) 、边( 调控作用) 组成的一个有向图结构。如图21 所示。图中每一个圆圈代表一个节 煳2i 简单g 目h 镕# 构i 意目 目22 ec 0 1 1 基目调控月络掏意目 点，也就是调控网络的元素，如基因。有向箭头表示表达增强作用，末端断线表示表达抑制 作用。在基因网络中，存在基因对自身表达的自调控的现象( 如图22 ) 。 2 1 2 蛋白质相互作用网络 在系统生物学领域的早期研究中，通过用酵母作为研究模型和其他一些有效实验手段， 发现许多调整和代谢途径至少部分地被保存在酵母或是更高的真核细胞中而且许多人类疾 病基因有酵母直向同源性。所以希望通过衡量和测定蛋白质蛋白质，蛋白质d n a 在基因组 睦安大学硕士学位论文 水平上的相互作用来解决发现蛋自质中的某 些功能性模块以及通过跟踪靶标蛋白质，实现 研制新药进而解决一些疑难病症。 大多数蛋白质与其它几个蛋白质的作用。 这种相互作用在图论的意义上看来是没有方 向的。为了达到某些目的，知道群中成员的识 别是有用的，或这比知道直接相互作用的合作 者更有用。因此可以用带标识的一些节点表示 蛋白质，它们之间用边来表示相互作用，通 过所连接起来的无向图来研究蛋白质相互作用 网络中的功能模块( 如图2 - 3 所示) 。 2 1 3 代谢路径网络 确定了所研究物种的所有代谢反应后，就可以根据所研究问题的需要，将代谢网络表示 成不同类型的图。在因特网上也存在着一些专门的代谢反应数据库，包含了与代谢网络中的 酶及其在不同物种中的编码基因相关的信息，其中最著名的数据库有k e g g ( h t t p ： w w g e n o m ea d j p & e g g ) ，e c o c y c ( h t i p ：l l c o ：”y c0 r g ) ，w i t ( h u p ：w i tm c s a n lg o v w i t ) 等。由这些 数据库可以方便地查到某一物种中所有的代谢反应；例如，可以从k e g g 下载催化某一物种 代谢反应的所有酶，以及所有物种的全部生化反应及其催化酶，由这两个数据库就可以很容 易地得出该物种中所有的代谢反应。代谢网络可表示为以下4 种类型的图： 第一种t 化合物 ( s u b s t r a t eg r a p h ) 。每个顶点对应一种化合物，若化合物a 能通过反应生 成化台物b ，则在这两个化合物对应的顶点连线。 第二种，反应图( r e a c t i o ng r a p h ) 。每个顶点对应一个反应，若反应a 的一个产物是反应b 的一个底物，则在这两个反应对应的顶点连线。 第三种，酶 图( e n z y m e c e n l r i cg p ”。每个顶点对应一个酶，若酶a 的一个产物是酶b 的 一个底物，则在这两个反应对应的顶点连线。 第四种，化台物一反应二部 ( s u b s t r a t e e n z y m eb i p a r t i t eg r a p h ) 。二部图的顶点有两类，仅 在不同类的顶点间有连线而同类的顶点间无连线。底物一反应二部图的一类顶点对应化合物， 另一类顶点对应反应，在反应与它的底物及产物问连线。 22 图及相关概念 图论是数学的一个分支，以图为研究对象。这种图由若干给定的点和连接两点的线构成， 借以描述某些事物之间的关系。用点代表事物，用连接两点的线表示两个事物之间具有特定关 系。 警瓮一笈y 蓠， 啦甏。一一 一蒸。一。m b 第二章生物网络的图论模型 2 2 1 图、子图、路径 图g 是一个二重组：g ( v ，e ) ，其中矿是非空有限集合，它的元素称为节点，e 也是( 可空) 有限集合，它的元素称为边。 有向图中，以节点，为始点的边数称为v 的出度，记为d e g + ( v ) ；以节点v 为终点的边数称 为v 的入度，记为d e g - ( ，) ；它们的和： d e g ( v ) = d e g + ( v ) + d e g 一( v ) 称为1 ，的度。 无向图中，与节点v 相关联的边数称为v 的度，记为d e g ( v ) 。 定义2 1 g = ( v ，e ) 为一个给定的图，称g = ( k ，e ) 为g 的子图，当且仅当k v 且 e e 。特别地，如果e 包含e 中所有连接k 中节点的边，则称g = ( k ，巨) 为g 的导出子 图。称图g 是连通的，如果g 的任意两个节点之间都存在路径。 特别指出，本文所要搜索的子图是指连通的导出子图，下文所提到的子图均指连通的导 出子图。 定义2 2 图g ( v ，e ) 的点边交替序列p = q m 乞巳屹称为g 的一条从v o 到u 的长为n 的路径，其中，弓= v 一，v e ( 扛1 ，2 ，n ) ；p 称为简单路径，如果与，e 2 ，巳互不相同；p 称 为基本路径，果v 0 ，m ，互不相同；p 称为回路，如果v o = 屹；回路p 称为简单回路，如 果q ，e 2 ，乞( v o ，v 1 ，v n ) 互不相同。 2 2 2 图的同构 定义2 3 对给定两个图g ( v ，e ) ，g ( y ，e ) ，若存在双射f ：v 一矿使对任意口，6 v ； ( 口，b ) ee 骨( 厂( 口) ，厂( 6 ) e ) ，并且( 口，b ) 和( 厂( 口) ，厂( 6 ) ) 有相同重数，则称g 与g 同构，记为 g 兰g 。 注：两图同构是相互的：g 兰g 营g 兰g 。 两图同构时不仅节点之间要有一一对应关系，而且要求这种对应关系保持节点间的邻 接关系对有向图同构还要求保持边的方向。 寻求判断图同构的简单有效方法仍是图论待解决的重要问题。 定义2 4 对具有m 个节点的图，按同构关系将其分成如干个类，称这样的类为等价类。 定义2 5 设g = ( v ，e ) 为具有m 个节点的图，t n 称阶矩阵a = ( ) 。煳为g 的连接矩阵，其 f 1 节点i 和j 有边相连 。“驴一10 节点i 和j 无边相连。 为了描述方便，本文将g 的第f 个节点记为f 。 8 长安大学硕士学位论文 2 2 3 频繁子图 在图g 中，存在大量具有相同( k 个) 节点的子图，将这些子国按同构关系进行分类， 并统计出各类子图的频率，频率较大( 太于某一阐值) 的子图即为频繁子图。 2 3 随机网络 在此对复杂网络理论。1 1 作简要介绍，为下一步模体挖掘研究做准备。 2 3 1 复杂网络 地球上任意两个人之间要通过多少个朋友才能认识? 万维网( w w w ) 上从一个页面到 另一个页面平均需要点击多少次鼠标? 层出不穷的病毒是如何在互连网上传播的? 各种传染 病是如何在人类和动物中流行的? 这些看上去各不相同的问题都涉及到复杂的网络，越来越 多的研究表面，这些互不相同的网络之间有许多惊人的相似之处。 鞲 互连网 社会刚络 食物f _ 司 目24 现实t # n 十复杂h 络1 ：意图 般而言，网络系绩的复杂性体现在以下几个方面： 结构复杂性，网络连接结构看上去错综复杂，极其混乱。 蛋白质相互作用网 第二章生物网络的图论模型 2 、节点复杂性，网络中的节点可能是具有分岔和混沌等复杂非线性行为的动力系统。 3 、各种复杂性因素的相互影响，实际的复杂网络会受到各种各样因素的影响和作用，例 如，耦合神经元重复地被同时激活，那么它们之间的连接就会加强，被认为是记忆和学习的 基础。 2 3 2 复杂网络研究的简史 1 7 3 6e f i l e r七桥问题 1 9 5 9e r d 6 s随机图理论 - 19 6 7m i l g r a m 小世界实验 1 9 7 3g r a n o v e t t e r弱连接的强度 19 9 8w a t t s 和s t r o g a t z 小世界模型 19 9 9 b a r a b ；i s i 和a l b e r t无标度网络 a b 2 3 3 复杂网络的重要的统计性质 度分布( t h ed e g r e ed i s t r i b u t i o n ) ：在网络中随机选取一若 个节点，该节点的度用x 表示，则随机变量x 的分布称为度分 布。图2 5 ( a ) ，图2 5 ( b ) 分别表示泊松分布和幂律分布。 如图5 1 中，社会网络和蛋白质相互作用网的度分布是不同 图2 5 ( a ) 的。 图5 2 ( b ) 图2 5 两种分布对比 聚集系数( t h ec l u s t e r i n gc o e f f i c i e n t ) ：节点i 的聚集系数c = 2 e ，( k j ( k , 一1 ) ) ，其中毛表示与节 点i 相连的节点数，e 表示与节点i 市目连的节点之间存在的连边数。聚集系数代表的是节点i 的 领域内节点之间连接的紧密程度。 平均路径长度( t h ea v e r a g ep a t hl e n 曲) ：平均路径长度l = 了 d u s ，其中d o 表示节点i 和j 的距离，s ：n ( n + i ) 2 ，n 表示图的节点总数。平均路径长度表示节点之间连接的平均距离。 表2 1 列出了一些复杂网络的统计性质。 表2 1一些复杂网络的统计性质表 网络对象规模平均度值( k )平均最短路径( l ) 平均聚集系数( c ) 医疗文献合作网 1 5 2 0 2 5 11 8 1 4 60 0 6 6 因特网3 0 1 5 6 2 0 93 5 2 4 1 1 3 7 3 7 6o 1 8 0 3 数学家合作网 7 0 9 7 53 9 9 50 5 9 e c o l i 基质图 2 8 27 3 5 2 90 3 2 e c o l i 反应图 3 152 8 3 2 6 20 5 9 2 3 4 随机网络模型 目前关于随机网络产生的模型【3 l 】主要有： l o 长安大学硕士学位论文 1 、完全随即网络( e r 模型) 【2 3 1 ，它是以完全相同的概率p 给每一对节点连上边，其度分 布可用泊松分布来描述。 2 、小世界模型( s w 模型) 2 4 】，其算法是先产生一个具有n 个节点的最近邻耦合网络， 再进行随机化重连，但它有可能破坏网络的连通性，从而提出了n w j 世界模型。 3 、无标度网络模型( b a 模型) 。【2 5 1 ，该模型是通过节点增长，优先连接( 根据已有节点 的度确定新增节点和已有节点的连接概率p r ) 。 4 、适应度模型2 6 1 ，它的算法思想类似b a 模型，在确定连接概率p 肘，引入了适应度分布 函数，比b a 模型更具有一般性。此外还有局域世界演化网络模型等。 每一种随机网络模型都有一定的特征，在生物网络模体发现问题中如何选择( 或建立) 随机网络模型，需要分析生物网络的产生机制。 2 4 生物网络的图论描述 生物网络数据记录的是系统内不同基因( 或蛋白质) 的属性以及衡量它们之间相互关系 的定量数据，这种数据可以利用图数据结构进行描述，这样，一个生物网络数据就可以转化 为由节点( 代表基因或蛋白质) 和边( 代表节点间的关系) 所构成的图。这样生物网络的功 能模块就对应这该土的一个( 或几个) 子图，功能模块的发现问题就转化为挖掘大图中具有 某种特点的子图，这种子图即为模体。 2 4 1 模块 模块( m o d u l e ) 是指一组物理上或功能上连接在一起的，共同完成一个相对独立功能的 节点，在生物网络中，它代表这生物系统具有一定生物功能的子系统，所以模块的发现问题 在系统生物学中具有重要的意义。 2 4 2 模体 模体( m o t i f ) 是指网络中出现频率较高( 相对于对应的随机网络) 的子图。近期研究表 明，模体是复杂网络的基本模块。 纵上所述，生物网络功能模块发现问题可以归结为挖掘对应图g 的模体，而模体又是一 个频繁的子图，这样，只要找出g 频繁子图，然后与对应的随机网络进行比较，就可以挖掘 出g 的模体，从而发现生物网络的功能模块。 2 5 总结 发现生物网络的功能模块的核心问题就是挖掘对应图的模体，这一问题包括2 个主要步 骤：1 、频繁子图挖掘，它包括子图搜索和同构分类两个问题；2 、产生对应的随机网络图， 比较真实网络和随机网络，从而去发现生物网络中功能模块。本文主要就第一个问题展开研 究。 第三章生物网络理论模型 第三章频繁子图挖掘算法 目前，频繁子图挖掘算法存在两个性能瓶颈：一是候选子图的产生，二是候选子图的频 率计算。要解决第一个问题，就是要高效的生成候选子图，即不会漏掉应有的，也不会产生 冗余的候选子图；第二个问题就是要高效的解决子图同构问题，而子图同构是一个n p 问题， 因此必须避免或者简化子图同构问题。先前的大多数图模式挖掘算法致力于找出所有的精确 频繁子图，但是在许多应用领域并不需要所有的子图模式，只需要少数有代表性的子图模式 即可。据此，本文提出了种高效率的频繁子图挖掘算法。 首先介绍已有的算法，然后详细描述本文提出的算法，本文算法包括四个主要内容：1 、 基于环分布的子图搜索算法，2 、基于矩阵特征值理论的子图同构算法，3 、基于度序列的子 图同构算法，4 、基于统计理论的子图频率计算。 3 1 图模式挖掘算法的类型 为了后续讨论的方便，我们将图模式挖掘算法按照不同情况进行分类： ( 1 ) 按照模式挖掘算法的输入数据类型进行分类：分为g r a p h t r a n s a c t i o n 和s i n g l e g r a p h 两种类型。g r a p h t r a n s a c t i o n 型模式挖掘所处理的输入数据是由许多规模相对较小的图构成的 集合，每个图可能只包含几十到几百个顶点；而s i n g l e g r a p h 型模式挖掘的对象则只有一个大 图，这个大图包含成千上万个顶点。这两种类型的区别还在于它们计算候选子图频度时所使 用的策略。g r a p h t r a n s a c t i o n 型计算模式在图集合每个图中是否出现，不管它在同一个图中出 现了多