基于对称子图和概率分层的网络模体发现算法研究

《基于对称子图和概率分层的网络模体发现算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学校代号：10532学密号：S11102041级：普通湖南大学硕士学位论文基于对称子图和概率分层的网络模体发现算法研究TheResearchonNetworkMotifsDetectionAlgorithmBasedonSymmetricSubgraphandLayeredProbabilitybyWEIMiaoB．E．(ChangshaUnivercityofScienceand7rechnology)20l0Athesissubmittedinpanialsatisfactionoftherequirementsforth

2、edegreeofMasterofEngineeringlnComputerscienceandteclulologyintheGraduateschoolofHunanUniversitySuperVisorProfessorLUOJiaweiMay，2014㈣2㈣8Ⅲm1吣5㈣0吣6㈣2㈣Y湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在

3、文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：jL采日期：刊争年占月‘日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1．保密口，在一年解密后适用本授权书。2．不保密囤。(请在以上相应方框内打”√”)作者签名：导师签名：卫么．日期：Ⅵ7lf年‘月?日

4、日期：少己f年铲6日基于对称子图和概率分层的网络模体发现算法研究摘要随着人类基因组学的研究已经取得巨大成就，生命科学研究重心已经从揭示生命遗传信息转移到分子整体水平对功能的影响，大量的生物网络数据也随之涌现。蛋白质相互作用网络是蛋白质相互作用关系的整体表达，是研究生物系统进化的关键。网络模体作为相互作用网络的基本组成单元，对蛋白质进化有重要影响。模体发现也逐渐成为蛋白质组学研究的热点问题。由于网络模体发现计算非常复杂，关于网络模体发现算法的研究大多是基于提高时间效率。本文在基于蛋白质相互作用网络的精确网络模体发现算法的研究中，

5、提出了旨在改善算法时间效率和抽样算法精确度的模体发现新方法。研究表明，网络中存在的对称结构会造成计算的冗余。因此本文提出了模体发现方法MDBS(MotifDetectionbasedonBasicSymmetricSubgraphs)，该方法利用基本对称子图BSs(BasicSymmetricSub伊aph)性质来减少模体发现过程的冗余计算。MDBS根据BSS性质挖掘网络中的基本对称子图，对网络进行对称压缩，同时在子图搜索的过程中，对部分具有相同拓扑结构的子图归类，减少了子图同构过程的时间消耗。通过在不同蛋白质相互作用网络的实

6、验表明，MDBS提高了模体发现的时间效率。抽样子图搜索减少了模体发现过程中的计算量，但同时抽样算法不可避免的抽样误差影响了结果的准确性，是抽样网络模体发现中主要存在的问题。本文从提高抽样方法的稳定性和精确度出发，提出一种新型的基于节点概率分层的抽样模体发现算法LaRalld—ESU。实验分析发现子图搜索结果集中节点频率跟节点的邻居节点度数之和(S啪ofNeighbors’Degrees，SoNDS)和节点的边聚集系数之和(SumofEdgeClusteringCoemcient，SoECC)相关。结合节点这两个特征，LaRaI

7、ld．ESU对网络中所有节点进行分层，对不同层次的节点赋不同的抽样概率，在子图搜索过程中通过比较随机概率和节点的层次概率值进行节点扩充。最后通过在真实蛋白质相互作用网络的实验表明，这种方法提高了抽样模体发现方法的稳定性和精确度。关键词：网络模体；蛋白质相互作用网络；子图搜索；子图同构；抽样方法II硕士学位论文AbstraCtAsthestudyofhumangenomicshasmadegreatachieVements，thefocusofresearchonlifesciencehasmoVedfromstudyingge

8、neticinfonnationoflifetoreVealthemoleculargeneticinformationhowtoaffecttheoVeraHleVeloffunctional，ala唱enumberofbiologicalnetworkdataalsobe