文档介绍：Research on theAlgorithms for Di "g。77 Motif inBioi g"Discovering Larger ottt works May 2010 东南大学学位论文独创性声明本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名:乃曲7日期:址石哆东南大学学位论文使用授权声明东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文档,可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外,允许论文被查阅和借阅,可以公布(包括刊登)论文的全部或部分内容。论文的公布(包括刊登)授权东南大学研究生院办理。研究生签名:地师签名: 日期:造』!!够摘要近年来,随着生物技术,尤其是高通量技术的发展,生物网络数据有了显著的增长,出现了很多的生物网络数据库,包括蛋白质反应网络,新陈代谢网络,基因调控网络,神经网络等,如何从这些浩瀚的生物网络中识别出与功能相关的结构是当前的一个研究热点,而如何从生物网络识别出模体是研究生物网络结构和功能的关键一步。模体是指在某个网络的多个不同部分出现的某一相互连接的子结构,其表达程度明显高于在随机网络中的表达。目前的模体识别方法主要有穷举法和抽样法,前者试图找出给定真实生物网络中指定大小的所有模体,然而随着子图的增大,候选子图的数量呈爆炸性增长,识别模体所需的时间急剧增长,同时,内存空间也呈爆炸性增长,程序很快因内存空间耗尽而崩溃,所以穷举模体识别方法只能识别小规模和中等规模的模体,面对稍大规模的模体无能为力。针对此问题, 抽样模体识别方法应运而生,抽样法降低了穷举法因为遍历访问子图空间而产生的高复杂度, 该类方法部分访问子图空间,显著地降低了时间复杂度和空间复杂度,但由于难以等比例抽样,产生了抽样偏置,以及调整该偏置而产生的额外计算复杂度,同时抽样模体识别方法还存在抽样概率难以精确分配的缺陷。针对这些问题,本文在传统的模体识别方法上进行了研究和拓展,首先提出了一种基于划分的子图搜索算法(Partition based SubGraph Finder,PSGF),该算法能够唯一,不遗漏, 高效地搜索给定真实生物网络中指定大小的所有子图,PSGF基于划分的思想,即任意两颗搜索树中的子图通过全局划分顶点来加以区分,同一棵搜索树中不同子树中的子图通过局部划分项点来加以区分,从而能够实现不重复性。PSGF在运行过程中仅仅在内存中维持一条搜索树中从根结点到叶结点的路径,所以具有较小的内存使用量。本文将PSGF应用到模体识别框架中,产生了一种新的穷举模体识别方法——基于划分的模体识别算法(Partiton work Motif Finder,PNMF),在UETZ数据集上成功识别了中等规模的模体,与同类方法相比,具有较小的时间复杂度和空间复杂度。针对抽样模体识别方法概率值难以精确分配的缺陷,本文还提出了一种基于度的概率分配算法(Degree based Probability Assign Algorithm,DP从)。相比于目前的随机分配方法,DPAA基于真实网络与随机网络的本质特征, 具有较小的抽样偏置。 ,本文提出的两种模体识别方法能有效地识别真实生物网络中的模体,相比于目前的方法,具有较小的计算复杂度和较小的抽样偏置。关键字生物网络,模体识别,子图挖掘,抽样 Abstract Inrecent years,along with thedevelopment ofbiotechnology,especially inhigh—throughput technology,work data hasincreased hasbeen workdatabases,including protein works,works,gene works and toidentify the structure which associated with thebiological functionsfrom these vast data iscurrently ahotresearchtopic,and how tofindmotifsfrom the work is akey step tostudy thestructureand fu