探析频繁子图挖掘算法及其在生物网络中的应用

《探析频繁子图挖掘算法及其在生物网络中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：TP3]I．12壤孝夫海硕士学位论文频繁子图挖掘算法及其在生物网络中的应用导师姓名职称申请学位级别董安国巨永锋敦授I，学Ⅲ士学科专业名称交通信息I程&控制论文提交日期9009年3月论文答辩FJ期2009年4月学位授予单位瞻曼大学答辩委员会主席!!!螫±型学位硷文评阅人曼圣南飙投谯摘要人类基因组计划的基本完成表明后基因组时代的到来。人类积累的大量的生物信息数据为揭开生命奥秘提供了数据基础，生物学研究的热点由对细胞内个别基因或蛋白质功能的局部性研究，转移到以细胞内全部的基因、蛋白质及代谢产物为整体对象的系统研究。对基因调控网络、蛋白质相互作用网络、代谢路径网络等结构及功能模块

2、的检测技术的研究，逐步把分子生物学推入系统生物学时代。基因与蛋白质通过网状的相互作用产生更高一级的功能模块，所以，通过数学建模来设计有效的算法，在生物网络中进行功能模块的挖掘和分析，将有助于更好地研究生物体自身的功能和不同生物体之间的进化关系，为分析理解生命基本规律提供依据。本文对基于图论的经典频繁子图挖掘算法进行了系统的研究和全面的总结，在此基础上提出了一种新的挖掘频繁子图的算法，该算法包含子图的搜索算法及同构分类算法。对子图搜索问题，提出了环分布的概念，并构造了基于环分布的子图搜索算法ESR(EnumerateSubgraphsbasedonRing)；对子图同构问题，利用度

3、序列和特征值构造了两种算法，分别用于对有向图和无向图的同构判别；利用同构算法对搜索出的子图进行同构分类，根据分类结果得到频繁子图。当网络规模比较大时，子图数量非常庞大，同构分类的工作量很大，为此又提出了随机归类算法和Hamilton子图的挖掘算法，以减少同构分类的运算量。随机归类算法是通过从子图集中随机地抽取一定数量的子图进行同构分类，是一种近似的算法；Hamilton子图的挖掘算法旨在挖掘特定类型(具有Hamilton回路)的子图，以减少搜索结果集。最后对5个真实生物网络进行了仿真实验研究，找出了不同规模的频繁子图，实验结果表明本文提出的算法优于现有的算法。关键词：数据挖掘，频

4、繁子图，同构，模体，算法，Hamilton子图AbstractThemajorcompletionofhumangenomeplanindicatethattheageofpost—genomeisfinallycoming．Theabundantbio．informationdatapeopleaccumulatedinrecentyearsprovidethebasicreferenceforrevealingthemysteryoflives，andthefocusofresearchinbiologyhavechangedfromthepartialresearchofi

5、ndividualgenesorproteinsincellstothesystemresearchbasedontheentiregenesandproteinsaswellasthemetabolicproducts．Theresearchonthestructureandthedetectiontechniqueongeneregulatorynetworks，protein-proteininteractionnetworksandmetabolicnetworkshavepromotedthemolecule-biologyagetothesystem-biologya

6、gestagebystage．GenesandproteinsCangeneratesuperiorityfunctionalmodulesbynettyinteractions，therefore，usingmathematicmodelingtodesignefficientalgorithmsforminingandanalyzingthemodulesishelptostudythefunctionsoftheorganismitselfandtheevolvementrelationsbetweendifferentspecies，andcouldprovidewarr

7、antsforanalyzingandunderstandingthebasicdisciplinesoflives．Inthispaper,someworksaredoneinthefrequentsubgraphmining．Someclassicalgraph—basedalgorithmsforminingfrequentsubgraphsaresystematicallystudiedandcomprehensivelysummarizedinthispaper．bas