基于基因组中motif预测算法研究

《基于基因组中motif预测算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号!里!墨!重庆邮电大学硕士学位论文论文提交日期至QQ旦生墨旦窒窒旦论文答辩日期垒QQ旦生墨月圣墨旦论文评阅人答辩委员会主席2009年5月22日独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重庞整虫太堂或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：叛殳签字日期：少一7f年厂月；2日学位论文版权使用授权书本学位论文作者完全了解重麽由E电太堂有关

2、保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权重庆自E电太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书)学位做储躲弓丕嗖聊躲诨生签字日期：砂一c『年歹月二z日签字日期：函哆年f月哲日重庆邮电大学硕士论文摘要基因组中的Motif预测算法研究结合了生物学、应用数学、计算机等学科领域，是当前生物信息学研究的一个热点。本文在研究Motif预测算法基础上，针对海量生物基因组数据库的查询搜索需求，改进了贪心EM算法用于Moti

3、f的预测和分析。Motif的预测首先将生物序列中的碱基或氨基酸转化成为字符串，在不同字符串序列中寻找最大公共子串，再通过生物学特征将这些字符串提取出来，与利用实验方法得到的海量生物信息数据库匹配。寻找最大公共子串的算法设计思想和数学模型是Motif预测的关键所在，目前常用的算法有模式驱动和序列驱动之分，本文主要是对序列驱动的代表算法EM进行改进。本文分别对常用的预测算法进行了算法分析研究和实验比较。首先，归纳总结常见Moitf模型和算法，应用模式生物的数据库信息进行实验验证，比较了各种算法工具对真实数据集中的预测。以Meme算法为基础，结合Gibbs采样和weeder等算法，对

4、实验结果进行比较。实验结果表明，Gibbs采样算法和Weeder算法分别具有预测长、短Motif效率高的特点，而Meme算法预测长度范围广，但准确度不高。其次，以Meme的来源EM算法为基础，将贪心EM算法作为研究对象，分析算法模型和特点，进行重新划分后并应用kd．树初始化参数的思想，然后改进算法。最后，本文对改进的贪心EM算法进行仿真。采用人工数据集、真实数据集进行测试，并用Meme和我们的算法进行对比实验，通过IC值和ROC曲线的比较对预测效果进行评估。结果证明，我们的算法较Meme有更好的预测性。关键词：Motif预测，Meme算法，贪心EM算法，kd．树，算法比较Abs

5、tractRecently’rearchonalgoritllITlofMotifingenomeh觞becomeahottopicinc岍entbioinfomaticsresearch，whichcombinesbiology，appIiedmamematics，computerscience觚dotherfields．Itmaimystudiestllecharacteristicsofv暑lriouSsearchalgorimmsinmeforec2ustofMoti￡Ouraimist0improveforecaStingalgoritlmls，锄deVentural

6、ly印pliesthemtosearchrelativeinf0珊ationinmaSsivebio．genomedatab觞e．IllMotifforec嬲tprocessincomputer'followingbaSesorproteinf如torsymbolsiIlbiologic甜∞quencesare戗msfo肋edint0characters仃ings，W

7、eusuaIlysearcht王lelargestcommonsub。stringsindi虢rentsequence矧ng，eX仃aCttllese嘶ngsaCcordingt0biologicalfeatll

8、re，趴dtllenmatchtlleminmassivebio．informationdatab嬲e．TheimproVementofforccaustingalgori‰锄desta【blistlrIlentofmathmaticalmodelhaVebecometllekeypointSi11motifforec嬲t．So细jtllerearet、Ⅳocommonalgoritlulls，includingmodel一鲥Ven锄dsequence．“vena190rithm．Astll