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

作     者：孙伟东 

作者单位：东北大学 

学位级别：博士

导师姓名：马宗民

授予年度：2011年

学科分类：0831[工学-生物医学工程（可授工学、理学、医学学位）] 0711[理学-系统科学] 07[理学] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：通用设备结构计算 图形处理器通用计算 开放阅读框架 重复查找 控制元件检测 后缀数组构造 倍增法 

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