学位论文 > 优秀研究生学位论文题录展示

异构机群系统上序列比对并行处理研究

作　者: 崔鑫
导　师: 钟诚
学　校: 广西大学
专　业: 计算机应用技术
关键词: 双序列比对 多序列比对 并行算法 异构机群系统 可分负载
分类号: TP301.6
类　型: 硕士论文
年　份: 2008年
下　载: 46次
引　用: 1次
阅　读: 论文下载
 

内容摘要


序列比对是生物信息学的核心研究内容之一,也是各种序列分析任务的基本方法。它研究序列之间的优化对应,即用一个距离函数或者相似分数来度量序列之间的相似性和非相似性。序列比对对研究分子结构与功能预测具有重要意义,因此其计算方法得到人们高度重视。在实际应用中,序列比对的规模很大,即使利用最快的串行比对算法也很耗时,因此需要设计高效的并行算法以快速求解这类问题。由于机群计算系统具有高性能和低成本的特点,所以在异构机群系统上研究序列比对算法的并行处理具有重要的现实意义。本文基于可分负载理论的最优原则,对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,提出一种双序列全局比对问题并行处理的最优分配策略,利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明,与平均分配策略相比,本文提出的最优分配策略进行双序列全局比对并行处理所需的时间明显缩短,并获得良好的加速和可扩展性。多序列局部比对是另一个重要的序列比对问题。本文针对处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,给定处理机分配顺序,基于可分负载理论提出一种多序列局部比对问题并行处理的最优分配策略,给定了处理机最优分配顺序,给出并行求解多序列局部比对问题所需时间的数学规划模型。异构PC机群系统上的实验结果表明,本文提出的最优分配策略进行多序列局部比对并行处理所需的时间比按平均分配策略的算法所需时间短,并获得良好的加速和可扩展性。

全文目录


摘要  4-6
ABSTRACT  6-10
第一章 绪论  10-28
  1.1 研究背景  10-12
  1.2 序列比对问题的相关概念  12-23
    1.2.1 序列比对问题的生物学背景  12-13
    1.2.2 序列比对的基本概念  13-14
    1.2.3 动态规划算法  14-15
    1.2.4 全局比对和局部比对  15-18
    1.2.5 空位罚分和替换矩阵  18-20
    1.2.6 启发式算法  20-23
  1.3 序列比对研究与发展  23-26
    1.3.1 国外研究现状  23-26
    1.3.2 国内研究现状  26
  1.4 论文的主要研究内容和贡献  26
  1.5 论文的组织  26-28
第二章 并行计算基础  28-37
  2.1 并行算法的概念和复杂性度量  28-30
    2.1.1 并行算法概念和分类  28-29
    2.1.2 并行算法的性能评价标准  29-30
  2.2 并行计算模型  30-33
    2.2.1 PRAM模型  30-31
    2.2.2 分布存储SIMD模型  31
    2.2.3 异步APRAM模型  31-32
    2.2.4 BSP模型  32
    2.2.5 LogP模型  32-33
    2.2.6 可重构MESH互联的光计算模型  33
    2.2.7 Cell Matrix模型  33
  2.3 机群系统概述  33-37
    2.4.1 机群系统特点  33-34
    2.4.2 机群系统分类  34-35
    2.4.3 机群技术发展现状  35-36
    2.4.4 机群系统的组建  36-37
第三章 双序列全局比对并行算法在异构机群上的设计与实现  37-48
  3.1 引言  37-38
  3.2 双序列全局比对串行算法  38-39
  3.3 可分负载理论与异构机群系统上双序列全局比对并行算法  39-44
    3.3.1 双序列全局比对并行处理的最优分配策略  39-41
    3.3.2 分配给从处理机的子序列长度和并行迭代次数的确定  41-44
  3.4 实验结果和分析  44-47
  3.5 本章小结  47-48
第四章 异构机群系统上多序列局部比对并行算法  48-57
  4.1 引言  48-49
  4.2 多序列局部比对算法的分析  49-50
  4.3 异构机群系统上BLAST算法的并行处理  50-53
    4.3.1 BLAST并行算法的设计与分析  50-52
    4.3.2 BLAST并行算法的序列串最优分配策略  52-53
  4.4 实验结果和分析  53-56
  4.5 本章小结  56-57
第五章 总结  57-59
  5.1 本文的主要工作和贡献  57
  5.2 下一步的工作  57-59
参考文献  59-63
致谢  63-64
攻读硕士学位期间参加的科研项目  64
攻读硕士学位期间发表/录用的学术论文  64

相似论文

  1. 频繁图结构并行挖掘算法的研究与实现,TP311.13
  2. 基于并行算法的模糊综合评价模型的设计与应用,TP18
  3. 基于视觉反馈与行为记忆的GPU并行蚁群算法,TP301.6
  4. GPU加速的仿射算术在几何设计中的应用研究,TP391.41
  5. 基于GPU的H.264到AVS视频转码并行设计,TN919.81
  6. H.264并行编码算法设计及其在GPU上的实现,TP391.41
  7. 基于ADSPTS201S的并行信号处理系统的设计与实现,TN957.51
  8. 基于小波变换的图像压缩并行算法研究,TP391.41
  9. 基于GPU的并行蚁群优化算法的研究与实现,TP301.6
  10. 木马网络通信特征提取技术研究,TP393.08
  11. 基于信息素强度的蚁群算法及其应用研究,TP301.6
  12. 基于MapReduce的聚类算法的并行化研究,TP311.13
  13. 面向星载计算机的容错并行算法研究与实现,TP302.8
  14. 生物多序列比对研究算法,Q7-3
  15. 激光能量沉积光路追踪法及其并行化,TN241
  16. 基于LBM的两相流数值模拟及其并行算法的实现,O359
  17. 基于树形计算结构的电力系统潮流并行算法研究,TM744
  18. D-TIN并行构建方法及其在地图综合中的应用研究,P283
  19. 图像匹配的并行算法研究,TP301.6
  20. 求解大规模支持向量机问题的并行算法研究,TP18
  21. 生物信息多序列比对算法研究,TP301.6

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com