CUDA计算技术在生物序列数据处理中的应用研究

发布时间：2020-10-24 16:05

　　 目前新的高通量DNA测序技术能够在很短的时间内以较低的成本生成大量的序列数据,生物序列的数据量正以爆炸式的速度快速增长。与此同时,计算机处理器的频率已接近理论极限,这意味着现存的串行算法很难像以前一样依靠频率的提高获得性能提升。并行处理技术成为解决这一效率差异的必然选择之一。由于GPU比CPU拥有更强的计算能力和更高的内存带宽,而生物序列数据又具有数据量大、数据结构简单的特点,本文采用基于数据并行处理指令体系的GPU众核计算技术来实现生物序列数据的廉价高效处理。本文根据复杂程度的不同,精心筛选出若干个经典序列分析问题作为并行处理的研究对象,分别给出高效的数据并行算法设计,并通过CUDA并行计算平台加以实现、分析和优化。本文的主要贡献总结如下： 第一,对CUDA计算涉及的软硬件并行体系结构特点进行了比较全面的研究。基于GPU属于SIMD并行指令体系的特点,总结并归纳了常用的基本数据并行操作,为并行算法的设计和实现提供了基本的参考和指南。 第二,针对生物序列分析研究中最基本的开放阅读框架问题,通过运用直接和间接并行化两种方法,完成了六读码框翻译算法和序列频率统计算法的高效数据并行设计与实现,展示了数据并行算法设计的特点以及GPU通用计算技术的优势和局限,并给出了GPU计算的并行加速模型,用以衡量并行化效率。本文基于直接转换的方法设计了具有高度并行性的适合于GPU执行的六读码框翻译算法,其执行速度要比串行算法快5倍左右。然而序列频率统计过程的并行化就无法这么自然的表达,因为这个过程中包含严重的并行访问冲突和延迟,只能采用以排序和计算前置和操作进行替代的间接并行化方法。该间接并行频率统计算法基本能够达到相应串行算法的效率。并行开放阅读框架算法总的执行效率为串行算法的2倍左右。 第三,针对序列测定和分析中的重复序列检测问题,提出了一种通过构造字典次序来快速完成超短精确重复查找的数据并行算法,该算法的效率要比目前的串行算法提高一个数量级。DNA序列中的重复区域对许多关键生物功能发挥着至关重要的作用,重复序列检测也是生物信息学中一个必须解决的基本问题。本文详细说明了一个基于CUDA平台的快速数据并行超短精确重复查找算法的设计和实现过程,并以这些超短重复为种子,进一步提出了启发式的海明距离和编辑距离重复测定的数据并行化方法,并给出了可行的并行线程调度方案。并行重复查找算法设计过程中采用的按串行代码功能区逐步完成并行化的方法,不但可以快速确定并行化过程中面临的瓶颈问题,进而判定整个算法的并行化难度,而且便于并行程序的设计、调试、分析和优化,可以作为现存大多数串行算法实现并行化处理的参考。 第四,针对后缀数组构造问题,提出了一种新的以排序方法替代传统分组策略的并行后缀数组倍增构造算法,其数据并行执行效率明显高于同类串行算法。后缀数组广泛应用于序列分析、字符串匹配和文本压缩等领域,近年来,有关后缀数组构造和应用算法的不断探索构成了计算机科学中一个非常活跃的研究领域。在对现有串行算法进行了全面的分析和对比之后,通过抽象和等效替换的方法提出了一种适合于GPU计算的且更为简洁的并行后缀数组倍增构造算法,不但能独立完成后缀数组的并行构造,还可与现存的串行倍增算法结合使用,以达到更高的执行效率(速度可以达到同类串行算法3倍以上)。实验结果表明该算法在解决实际应用问题时,具有易于实现、执行速度快和可扩展性强等优点,是目前最快的单机运行算法之一。尤其是在处理小字符集的生物序列数据时,快于目前所有的串行算法。
【学位单位】：东北大学
【学位级别】：博士
【学位年份】：2011
【中图分类】：Q811.4;TP338.6
【部分图文】：

东北大学博士学位论文 第1章绪论1.1研究背景与动机自从1980年，英国和美国的生物化学家Frederick Sanger与Walter Gilbert发明DNA测序技术，DNA测序技术的发展取得了长足的进步，同时也产生了大量的序列数据。特别是2005年高通量并行测序技术逐渐成熟以来，不但测序的速度得到了近百倍的提升，而且测序的成本也下降了几个数量级，目前每兆序列的成本低至1美元。同时，人们惊奇的发现在半导体技术领域为人们所熟知摩尔定律同样适用于基因组测序领域，如图1.1所示的Genbank数据库中历年存储的序列数量新一代DNA测序技术操作更便捷，费用更低廉，这些特点推动了测序技术由大型测序中心向广大研究单位和医疗机构的普及。今后，各种测序技术可能成为一项广泛使用的常规实验检测手段，甚至个人基因组时代已为期不远，这将给生物学和医学等领域带来革命性的变革[16，17，37，38]。

(Power wall)、内存墙（Memory wall)和指令级并行度 ILP 墙（Instruction-LevelParallelism)的限制，近年来已呈现明显放缓的趋势，如图1.2所示_。自2002年到2006年，五年的时间单核处理器的性能只增加了的一倍，远远低于摩尔定-2-

图2.1 CPU和GPU的fy:秒浮点运算次数和存储器带宽Fig 2.1 Floating-point operations per second and memory bandwidth of CPU and GPU综上所述，结合生物序列数据的特点，本文采用基于图形处理器GPU的新
【参考文献】

相关期刊论文 前2条

1 孙伟东;夏秀峰;马宗民;;利用数据库实现分布式任务的程序和数据存储[J];航空电子技术;2009年01期

2 孙伟东;王微微;马宗民;;噬菌体基因文库控制元件测定的并行处理方法[J];沈阳航空工业学院学报;2010年05期

本文编号：2854682