DNA序列比对并行算法研究及应用

发布时间：2017-06-20 07:06

  本文关键词：DNA序列比对并行算法研究及应用，，由笔耕文化传播整理发布。

【摘要】：生物信息学(Bioinformatics),指的是利用信息技术和计算机科学等方法,以研究大量而复杂的生物数据的一门交叉学科。目前,基因组学中的DNA排序问题的研究是生物信息学的重要研究领域之一。研究DNA序列的基本途径是序列比对,它通过序列的排列规律寻找序列间的相似性和同源性,从而分析研究生物的遗传进化信息。近年来,随着生物学的发展,基因序列数据量成倍增加,传统的串行序列比对算法无法满足日益扩大的数据规模的需要。本文基于序列比对算法的特征研究其并行算法,提出一种序列编码算法和数据“首条序列划分”法,以有效提高算法的并行效率,为解决大规模生物序列比对问题奠定基础。本文主要的创新性工作包括:(一)提出一种新的DNA序列编码算法,实现基于MPI的并行FED算法。本文分析比较了DNA序列中精确比对(Exact Sequence Alignment)类型的算法,发现随着数据量的增长,算法计算时间会显著增加。为了解决这一问题,首先,我们提出了一种基于位运算的序列编码方式,以此降低数据存储空间,加快序列编码速度,从而提高算法效率;然后,采用并行算法对FED算法进行改进,并通过消息传递模型(MPI)在集群环境下实现算法的并行化,实验表明,该并行算法在20核环境下运行时,加速比达到16.1。(二)提出最适合CVoting算法的“首条序列划分”法,并基于MPI实现算法的并行。本文研究了模体发现问题(Motif Finding Problem)中计算挑战实例的算法,CVoting是目前具有代表性的能解决大型挑战实例的算法,但是它计算(21,8)挑战实例的时间依然需要超过20小时。因此,本文基于MPI的特点,设计三种数据划分方法,分析和比较三种方法对算法的适应性,提出“首条序列划分”方法是适合CVoting算法并行的最佳方式。该方式不仅实现算法的并行,将(21,8)挑战实例的运算时间降低到20分钟以内,而且算法从1个计算核开始一直到128个计算核始终保持加速比的线性增长,其中,在128核时加速比达到96.2。
【关键词】：并行计算 DNA序列比对 模体发现 MPI
【学位授予单位】：上海大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：Q811.4;TP338.6
【目录】：

• 摘要6-7
• ABSTRACT7-11
• 第一章 绪论11-17
• 1.1 研究目的与意义11-12
• 1.2 国内外研究概述12-14
• 1.3 本文的研究内容14-15
• 1.4 本文的组织结构15
• 1.5 本章小结15-17
• 第二章 并行计算概论17-28
• 2.1 并行计算机发展历程17-21
• 2.1.1 并行计算机系统17-19
• 2.1.2 并行计算机分类19-21
• 2.2 并行算法设计与评估方法21-23
• 2.2.1 并行算法设计21-22
• 2.2.2 并行算法评估方法22-23
• 2.3 并行算法编程23-26
• 2.3.1 并行编程模型分类23-24
• 2.3.2 主流并行编程模型介绍24-26
• 2.4 本章小结26-28
• 第三章 基于MPI的DNA序列比对并行算法28-43
• 3.1 FED算法介绍29-34
• 3.1.1 DNA序列比对算法29-30
• 3.1.2 序列编码方式30-32
• 3.1.3 比对算法32-34
• 3.2 FED算法的改进与并行化34-39
• 3.2.1 改进序列编码算法34-37
• 3.2.2 FED并行算法37-39
• 3.3 实验数据与结果分析39-42
• 3.3.1 实验环境39
• 3.3.2 实验数据和结果39-41
• 3.3.3 实验结果分析41-42
• 3.4 本章小结42-43
• 第四章 模体发现算法的并行化43-59
• 4.1 模体发现问题43-45
• 4.1.1 算法类型与发展现状43-44
• 4.1.2 问题的提出与相关定义44-45
• 4.2 Cvoting算法45-47
• 4.2.1 Voting算法介绍45-46
• 4.2.2 候选模体集计算46-47
• 4.3 Cvoting算法的并行化47-53
• 4.3.1 数据划分方式设计48-50
• 4.3.2 数据划分方式比较50-53
• 4.4 实验数据与结果分析53-58
• 4.4.1 实验环境53-54
• 4.4.2 实验数据和结果54-57
• 4.4.3 实验结果分析57-58
• 4.5 本章小结58-59
• 第五章 总结与展望59-61
• 5.1 结论59-60
• 5.2 展望60-61
• 参考文献61-67
• 作者在攻读硕士学位期间公开发表的论文67-68
• 作者在攻读硕士学位期间所作的项目68-69
• 致谢69

【共引文献】

中国期刊全文数据库 前10条

1 关亚林;曾艳奇;逯贵祯;;基于并行计算环境的混波室三维仿真[J];中国传媒大学学报(自然科学版);2008年03期

2 程克非;罗江华;李红波;;一种新的基于HPM并行计算性能数据采集方法[J];重庆邮电大学学报(自然科学版);2011年01期

3 王结臣;王豹;胡玮;张辉;;并行空间分析算法研究进展及评述[J];地理与地理信息科学;2011年06期

4 阮定益;;并行式matlab平台搭建[J];电脑知识与技术;2008年08期

5 胡海峰;;树状成本估算模型的并行处理[J];电脑知识与技术;2009年28期

6 古奋飞;王良侠;;浅析Linux集群技术[J];电脑知识与技术;2010年06期

7 古奋飞;王良侠;张莉;;基于Linux集群的高性能低成本的校园网解决方案[J];电脑知识与技术;2012年02期

8 李焱;胡祥云;金钢燮;吴桂桔;廖国忠;王程;;基于MPI的一维大地电磁并行计算研究[J];地球物理学进展;2010年05期

9 李焱;胡祥云;吴桂桔;叶益信;廖国忠;;基于MPI的二维大地电磁正演的并行计算[J];地震地质;2010年03期

10 刘晓群;邹欣;范虹;;基于并行云计算模式的建筑结构设计[J];电子技术应用;2011年10期

  本文关键词：DNA序列比对并行算法研究及应用，由笔耕文化传播整理发布。

本文编号：464763