生物序列比对算法的并行优化设计与实现

发布时间：2017-08-17 20:36

  本文关键词：生物序列比对算法的并行优化设计与实现

  更多相关文章： 双序列比对 并行化算法 多序列比对 后缀树

【摘要】：生物序列比对是生物信息学的基础和核心,随着生命科学的迅猛发展,需要研究的蛋白质和核酸序列的信息显著增加。常见的双序列比对串行算法时间复杂度为O(N2),多序列比对时间复杂度更高,随着序列长度的增加和比对规模的扩大,时间开销难以接受。在此情况下如果能够挖掘算法的潜在并行性,通过数据划分、流水处理等方式将算法并行化,使其在多个处理器上并行执行,可以大大提升算法效率。本文首先对生物序列比对和并行算法的相关概念进行了介绍。采取流水处理方式,将Needleman-Wunsch算法进行并行化设计。在此基础上提出了多个序列比对算法的并行化方法。通过找到多个checkpoint将矩阵划分若干部分,为每个处理器分配矩阵的一个部分,使各处理器并行执行子矩阵的Hirschberg算法并对完成后的结果进行整合,将Hirschberg算法进行并行化;通过提出使用活动结点和活动结点链表创建后缀树的方法,使按分支并行构建后缀树和按分支获取最大唯一匹配可以并行执行并且摆脱了对后缀链表的依赖,之后并行对锚点间的空位进行合并,将MUMmer算法进行并行化;通过对角线并行方式并行获取和扩展热点区域,采取将距离矩阵进行分块方式使多处理器并行获取不同对角线上热点区域的距离长度,将FASTA算法进行并行化;通过距离矩阵分块方式并行获取序列两两比对的距离长度,以及并行从进化树的叶子向根进行合并的方式,将Clustal W算法进行了并行化。最后对上述4种算法及并行化算法分别进行了实现,将串行算法运行时间与双核及四核条件下并行算法的运行时间进行了比对。实验结果证明了并行化算法比串行化算法速度得到了很大提升,并且得到了不错的加速比,更适用于多核结构。
【关键词】：双序列比对 并行化算法 多序列比对 后缀树
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：Q811.4;TP301.6
【目录】：

• 摘要4-5
• Abstract5-8
• 第1章 绪论8-13
• 1.1 课题的研究背景和意义8
• 1.2 国内外研究现状8-12
• 1.2.1 常用序列比对算法9-10
• 1.2.2 并行序列比对现状10-12
• 1.3 论文的主要内容12-13
• 第2章 序列比对和并行计算13-27
• 2.1 序列比对13-18
• 2.1.1 全局比对14-16
• 2.1.2 局部比对16-18
• 2.1.3 近似比对18
• 2.1.4 多序列比对18
• 2.2 序列比对相关知识18-22
• 2.2.1 后缀树18-21
• 2.2.2 利用后缀树进行字符串匹配21-22
• 2.3 并行计算22-26
• 2.3.1 OPENMP简介23
• 2.3.2 Needleman-Wunsch算法并行化23-25
• 2.3.3 分析算法的潜在并行性25-26
• 2.4 本章小结26-27
• 第3章 双序列比对算法的并行化设计27-47
• 3.1 Hirschberg算法的并行化设计27-31
• 3.1.1 Hirschberg算法步骤27-29
• 3.1.2 Hirschberg算法并行化29-30
• 3.1.3 实验结果和分析30-31
• 3.2 MUMmer算法的并行化设计31-40
• 3.2.1 MUMmer算法步骤31-33
• 3.2.2 MUMmer算法并行化33-39
• 3.2.3 实验与实验结果分析39-40
• 3.3 FASTA算法的并行化设计40-45
• 3.3.1 FASTA算法步骤40-42
• 3.3.2 FASTA算法的并行化42-45
• 3.3.3 实验与分析45
• 3.4 本章小结45-47
• 第4章 多序列比对算法的并行化研究47-53
• 4.1 Clustal W算法步骤47-50
• 4.2 Clustal W算法的并行化50-51
• 4.2.1 距离矩阵的并行化获取50-51
• 4.2.2 通过进化树获取多序列比对结果51
• 4.3 实验与分析51-52
• 4.4 本章小结52-53
• 结论53-54
• 参考文献54-58
• 攻读学位期间发表的学术论文58-60
• 致谢60

【参考文献】

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

1 陈润生;生物信息学[J];生物物理学报;1999年01期

，

本文编号：691000