生物序列相似性搜索算法研究与实现

《生物序列相似性搜索算法研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Ｓｏｕ化ＣｈｉｎａＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ工程硕±学位论文生物序列相似性搜索算法研究与实现作者姓名工程领域车別牛工程校内指导教师汤德佑副教授校外指导教师沈顺走高级工程师所在学院软件学院论文提交日期２０１６年３月ResearchandImplementationforSimilaritySearchAlgorithmofBiologicalSequencesADissertationSubmittedfortheDegr

2、eeofMasterCandidate：LiJuanSupervisor：A.P.TangDeyouS.E.ShenShunqiSouthChinaUniversityofTechnologyGuangzhou,China分类号：TP3学校代号：10561学号：201321033559华南理工大学硕士学位论文生物序列相似性搜索算法研究与实现作者姓名：李娟申请学位级别：工程硕士工程领域名称：软件工程校内指导教师姓名、职称：汤德佑副教授校外指导教师姓名、职称：沈顺七高级工程师论文形式：□产品研发□工程

3、设计应用研究□工程/项目管理□调研报告研究方向：软件工程技术论文提交日期：2015年03月23日论文答辩日期：2016年03月25日学位授予单位：华南理工大学学位授予日期：年月日答辩委员会成员：主席：韩国强委员：张平健陈仲驹罗荣华陈虎华南理工大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所。取得的研究成果除了文中特别加Ｗ标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中明

4、确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：％飾曰期：办＾年０＞月巧曰学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定；，良Ｐ研究生在校攻读学位期间论文工作的知识产权单位属华南理工大学。学校有权保存并向国家有关部口或机构送交论文的复印件和电子版，允许学位论文被查阅（除在保密期内的保密论文外）；学校可公布学位论文的全部或部分内容，可Ｗ允许采用影印、缩印或其它复制手段保存、汇编学位一致论文。本人电子文档的内容和纸质论

5、文的内容相。本学位论文属于：□保密，在年解密后适用本授权书。囚不保密，同意在校园网上发布，供校内师生和与学校有共享协议的单位浏览；同意将本人学位论文提交中国学术期刊光盘版）电子杂志化全文出（版和编入ＣＮＫＩ《中国知识资源总库》，传播学位论文的全部或部分内容。＂＂请在［＾上相应方框内打Ｖ（）巧、．巧作者签名：舍觀日斯ｚｗ６自：：指导教师签名：曰期：作者联系电话：摘要生物序列相似性搜索是基因组学和蛋白质组学研究的基础，其性能取决于双序列比对算法。FASTA和

6、BLAST是常用的生物序列相似性搜索软件，采用了局部序列比对的思想，取得了较好的效果，但比对结果不足以体现序列间的全局相关性。本文针对双序列的全局比对问题，研究了基于蚁群算法的双序列比对的优化方案和并行化方案，并将其应用于生物序列的全局相似性搜索。论文的主要贡献如下：1.给出了蚁群算法求解双序列比对的优化方案。针对蚁群算法求解双序列比对问题的特点，从状态转移规则、比对得分映射规则、缓存等方面进行优化以提高比对的灵敏度和速度。实验结果表明，当序列长度为1050时，改前后算法时间比为1.92，Need

7、leman-Wunsch算法与改进后算法时间比为5.72，且序列越长时间比越大。2.给出基于改进后的算法求解双序列比对问题的并行化方案。a)给出了基于消息通信模型的并行化方法，给出了适合并行的子蚁群大小、迁移周期和迁移内容方案。通过子蚁群之间交流最优解，该方法不仅得到较高的加速比，还提高了解的质量。实验结果表明对于长度为1050的序列，采用2个节点，每个节点蚁群大小为9时，解的平均质量接近最优解，并行效率达到90.9%。b)给出了基于共享内存模型的并行化方法。通过分析改进后算法的速度瓶颈，对耗时最

8、多的“搜索比对路径”和“信息素更新”两个步骤完成了并行化。实验结果表明，8线程并行情况下，加速比达5.09，且序列越长效率越高。3.将改进后的算法应用于求解生物序列全局相似性搜索并给出并行化方案。a)设计了筛选规则，筛选出有可能和查询序列相似度高于设定阀值的有效序列集，避免不必要的时间消耗。b)结合使用改进后算法的两种并行化方案，给出了串行搜索-并行比对方案。该方案不仅能够得到较高的加速比还可以提高解的质量，适用于对灵敏度要求较高的情况。c)给出并行搜索-串行比对方案。根据蚁群算法