改进的网络模体发现算法及模体功能分析

《改进的网络模体发现算法及模体功能分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、改进的网络模体发现算法及模体功能分析作者姓名赵欣蒙指导教师姓名、职称张军英教授申请学位类别工学硕士学校代码10701学号1403121726分类号TP30密级公开西安电子科技大学硕士学位论文改进的网络模体发现算法及模体功能分析作者姓名：赵欣蒙一级学科：计算机科学与技术二级学科：计算机应用技术学位类别：工学硕士指导教师姓名、职称：张军英教授学院：计算机学院提交日期：2017年6月AnImprovedMethodforNetworkMotifDetectionandMotifFunctionAnalysisAthesissubmittedtoXIDIANUNIVERSITYinpartialfu

2、lfillmentoftherequirementsforthedegreeofMasterinComputerApplicationTechnologyByZhaoXinmengSupervisor:ZhangJunyingProfessorJune2017西安电子科技大学学位论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工

3、作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文若有不实之处，本人承担一切法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。学校有权保留送交论文的复印件，允许查阅、借阅论文；学校可以公布论文的全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，获得学位后结合学位论文研究成果撰写的文章，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要随着生物信息学

4、研究进入后基因组时代，序列数据的模体概念拓展到了网络层面，网络模体的概念应运而生。网络模体被定义为网络中频繁且独特的子图模式，它在目标网络中出现次数远超过随机网络。网络模体作为构建网络的重要功能模块，引起众多领域的广泛关注。对于网络模体发现问题，目前研究者们已经提出了诸多算法，在识别小规模的模体时这些算法的性能较好，但随着待搜索子图规模和网络规模的增大，子图搜索和同构子图查找的计算复杂度显著提高，很多算法都无法满足科学研究的时间需求。此外，目前关于网络模体的文献大多与模体的发现算法有关，而很少涉及到对模体的功能分析。对模体进行功能分析可以让我们对网络模体的认识更加深入，使得网络模体在认识网络

5、和分析网络的过程中发挥重要作用。所以，当务之急是积极探索更加高效的网络模体发现算法并对模体功能进行有效分析。通过分析现有算法的不足，本文提出了一种改进的网络模体发现算法。算法中提出了一种新的基于局部结构特征表示输入图的方法，能够更快速准确地提取输入图的拓扑结构特征，然后通过改进的近邻传播聚类算法对提取的特征进行聚类，并通过提出的模体判定标准对聚类结果做进一步处理以发现网络模体。论文中通过设计合理的仿真实验验证了算法发现网络模体的有效性。在来自不同研究领域的8种真实网络数据分别实验，只需要数秒的运行时间，和Kavosh、FANMOD、MFinder等多种模体发现工具及算法的实验比较，显示了本文

6、算法的高运行效率，而且算法不仅正确识别出了目前已发现的多种模体，还发现了其他结构的模体。论文最后还介绍了GO和DAVID两个常用的功能分析工具，重点讨论了用于模体分析的两种主要方法：功能注释分析和富集分析，并在大肠杆菌转录网络调控的3种模体上进行了功能分析，分析结果表明它们都显著富集在某些特定功能。关键词：网络模体，网络模体发现，模体功能分析I西安电子科技大学硕士学位论文IIABSTRACTABSTRACTWiththeenteringofbioinformaticsresearchintopost-genomeera,thenotionofmotifsusedforsequencedata

7、hasbeenexpandedtothelevelofnetworks,andthereforetheconceptofnetworkmotifsappears.Networkmotifisdefinedasafrequentanduniquesubgraphpatterninanetworkthatoccursmuchmorefrequentlyinthetargetnetworkthaninrandomn