基于Gibbs抽样的有约束多项分布模体识别算法.pdf

《基于Gibbs抽样的有约束多项分布模体识别算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、代号10701学号0821421386分类号TP301.6,Q78密级公开题（中、英文）目基于Gibbs抽样的有约束多项分布模体识别算法PositionDependenciesbetweenMultinomialDistributionforMotifDiscoveryBasedonGibbsSampling作者姓名王围指导教师姓名、职称刘立芳副教授学科门类工学学科、专业计算机软件与理论提交论文日期二○一一年四月创新性声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果．尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论

2、文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料．与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意．申请学位论文与资料若有不实之处，本人承担一切的法律责任．本人签名：日期关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学．学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文．同时本人保证，毕业后结合学位论文研究课题再攥写的

3、文章一律署名单位为西安电子科技大学．（保密的论文在解密后遵守此规定）本学位论文属于保密，在年解密后适用本授权书．本人签名：日期导师签名：日期摘要摘要模体识别是生物信息学的重要研究领域。它通过寻找不同序列间的相似片段来归结出这些序列片段中所蕴涵的特征模体，从而揭示生物序列数据中所蕴涵的生物学意义。最近的生物实验表明，部分模体内部各位置之间存在明显的相关性约束关系，但目前的很多算法却没有考虑模体内部的相关性约束。本文首先介绍了课题背景，阐述了本课题的研究目的及意义，介绍了一些典型的模体识别算法。然后介绍了通过假设检验判断模体内部位置间相关性约束的方法；将模体相关性约束加入到Gibbs算法之

4、中，实现了具有位置相关约束的Gibbs2算法，该算法被命名为SimiMotif。该算法通过χ检验和Fisher精确检验的运用，实现了模体内部位置相关性约束的判定，然后使用被命名为Simi_link的一维数组来表达模体内部的相关约束关系。算法利用PFW模型以及Simi_link来共同表达模体模型，通过新的Gibbs打分函数进行模体识别过程，并且能够识别多个模体以及多个模体实例，选择与背景最具显著性差异的几个模体输出。然后本文将二维相关性约束推广到多维，提出MultMotif算法。最后将SimiMotif以及MultMotif算法和对应SimiMotif算法过程相同但是去掉相关约束部分的模

5、体识别算法，分别进行了对Tompaetal.于05年提出的基准库以及Sandveetal.于07年提出的基准库这两个基准测试库上的测试，然后将SimiMotif以及MultMotif同已有的多种模体识别方法进行了比较。实验结果表明SimiMotif以及MultMotif算法所用的相关约束模体模型能够较好地表达模体模型，并且算法在一定程度上提高了识别的准确度，两者在Tompaetal.基准库所对比的17种方法中主要参数分别排第六以及第五位，如何进一步改进准确度并且提高算法执行效率将是一轮新的工作。关键词:生物信息学模体识别Gibbs抽样χ²检验Fisher精确检验AbstractAbst

6、ractMotifdiscoveryisacentralchallengeofbioinformatics.Itgetsthecharacteristicmotifhidedinthesequencebyfindingthesimilarsegmentinthedifferentsequencestorevealthebiologicalmeaninghidedinthesequence.Recentbiologicalexperimentssuggestedthatthereexistsdependencyamongpositionsinsomemotifssignificantly

7、.Butnumbersofmotifdiscoveryalgorithmtodaydidn’tconsiderthedependency.Inthispaper,thebackground,thepurposeandtheimplicationofthetopicsarepresentedbriefly.Then,wedescribesometypicalmotifdiscoveryalgorithm.AGibbssamplingbasedal