论文部分内容阅读
高通量测序技术的不断发展为生物学研究提供了丰富的生物数据信息的同时,生物数据信息爆炸式增长所带来的海量数据也给科学研究带来了新的难题。处理如此大量的数据,必须采用更高效、更方便、更实用的方法,才能配合生物学研究,共同提高科研工作的效率。 序列比对技术是处理生物信息最常用的手段,通过序列比对找到序列之间的同源性、相似性等对生物学研究有着及其重要的意义。目前,已有许多处理序列比对问题的方法,最经典的比对方法是Smith和Waterman提出的smith-waterman算法,该方法是一种基于动态规划理论的局部比对算法,其计算结果十分准确,但是smith-waterman算法的空间复杂度和时间复杂度很高,随着计算数据越来越庞大,在传统的串行架构下,该方法计算效率很低,严重影响了科研效率。 如GPU并行计算等计算机多核心技术的不断发展,使得并行计算在处理大数据问题时显现出越来越明显的优势。本文使用GPU并行技术,在最新的CUDA架构下针对海量生物序列数据的序列比对问题,结合已有的串行和并行算法,基于经典的Smith-Waterman算法,提出一种基于序列向量化的两级并行序列比对方式,该方式通过并行序列向量化、并行聚类近似比对、并行Smith-Waterman算法比对这三个环节,先近似比对缩小比对序列规模、提高比对计算效率,再使用精确比对来保证序列比对精度,从而提高该比对方式的综合性能。另外,针对并行Smith-Waterman算法,本文提出了一种改进思路,通过异步并行的方式提高处理器核心的使用效率,进一步提升Smith-Waterman算法的计算效率。同时,针对生物信息序列库多样性序列分析中的高通量序列比对问题,给出了具体的实验方案与结果分析,并进一步讨论了并行序列比对算法在序列比对过程中的设计思想。