论文摘要
从人类基因组计划实施开始,生物计算包括的理论,方法以及相关的应用被越来越多的生物,医学以及其他医务工作者所需要和关注。生物计算作为一个交叉学科,它的发展与研究越来越凸显出重要的作用。蛋白质,蛋白质组,基因,基因组等生物学信息的数据采集,存储与分析及其生物学意义,是生物计算乃至生物,医学,医药的重点研究内容之一。随着测序技术的发展,生物数据的规模呈现爆炸式增长的趋势。如基于第三代测序技术的Helicos公司,测序仪每天可以产出3GB的基因数据。此外,随着测序技术的发展,序列的长度也在急剧的增长。无论是数据的规模还是数据的长度,都给生物计算提出了新的挑战。针对蛋白质数据和基因数据开发的生物应用程序,大多是基于传统的CPU平台,而且是基于单线程进行开发设计的。因此,为了处理更多的数据,就需要增加大量的硬件设备来处理。这就大大提升了生物序列分析的成本。从1986年到2002年,微处理器的性能以5050%的速度不断提升。但是2002年之后,单处理器的性能提升速度下降到每年大约20%。所以从2005年开始,大部分主流的CPU制造商决定采用并行处理来快速的提升微处理器的性能。因此如今单个CPU可以包含多达十几个计算核心。与此同时,也出现了大量的计算设备,如图形处理器GPU,集成众核架构Xeon Phi,可编程门阵列FPGA等等。借助不断提升的计算能力和新的计算设备,人类在诸多领域,如气候模拟,蛋白质折叠,药物发现,能源研究,人类基因解码,人工智能等领域发展的非常迅速。围绕着基因数据和DNA序列比对过程,本文的研究内容主要分为三个部分。第一部分基于众核架构Xeon Phi,设计并实现了高效的并行DNA序列比对验证算法MyPhi。第二部分针对DNA序列比对的过滤阶段,我们提出了全新的过滤算法PUNAS,并给出了基于多核平台和众核平台可扩展的并行化实现。基于前期的工作,最终我们设计了一个完整的DNA序列比对软件FEM。相较已有的DNA序列比对软件,FEM在内存的使用以及运行时间两个方面都有所提升。为了加速DNA序列比对的验证阶段,我们首先在算法上做了深入的调研。相较于传统的Smith-Waterman算法,基于位并行的Myers算法效率更高。Myers算法的主要思想是将Smith-Waterman中计算矩阵单元格的绝对值策略转换为计算相邻矩阵单元格的差值的策略,再将差值用若干个比特向量表示。基于第一代和第二代的Xeon Phi平台,我们设计并实现了高效的并行Myers算法,MyPhi。为了充分利用多核计算能力,我们用OpenMP并行编程模型实现了多线程并行。在细粒度上,我们设计了多种并行方案,通过实践对比不同并行方案的优缺点,选择最优的并行方案。再结合每一个众核平台上特定的向量指令集,实现了核心计算部分的向量化优化。实验表明,MyPhi在单个KNL设备上实现了TCUPS（Trillions cells update per second）的性能。对于DNA序列比对软件来说,验证阶段占了90%的总运行时间,因此MyPhi算法可以提升DNA序列比对过程的效率。SHD,移位海明距离算法,是对Myers算法的一次改进。由于在DNA序列比对过程中,只有一少部分的比对过程是有意义的,用来0为DNA序列找到正确的比对位置。因此一些快速的启发式算法可以用来快速的过滤掉大部分没有意义的比对。SHD算法作为Myers算法的一种近似,属于这种高效的启发式算法,也被称为过滤算法。在时间复杂度上,Myers算法是平方级别的,而SHD算法具有线性的时间复杂度。我们通过调研SHD算法,在保证不改变算法意义的前提下,通过改变计算的方法,大大的降低了算法的复杂度,使得算法的操作步骤由原来的35步减少到了13步。我们将改进之后的算法称为PUNAS算法。PUNAS算法不仅计算效率更高,而且已经进一步扩展到支持任意长度的DNA序列比对。另外,针对多核架构,如SSE,AVX,以及众核架构Xeon Phi等,我们都给出了算法在该硬件平台上的实现,可见PUNAS算法具有很好的平台可扩展性。实验表明,PUNAS算法的计算性能比Smith-Waterman算法快了几千倍。此外,相较于ScqAn等比对软件中使用的Myers算法,SHD算法也取得了7.3倍的加速比。基于已有的工作,为了加速DNA序列比对过程,我们设计并实现了一个完整的DNA序列比对软件FEM。与以往的DNA序列比对软件不同的是,FEM在创建哈希索引过程中提出了新的数据结构和新的算法。FEM中使用的精简哈希索引通过仅记录参考基因中的部分位置。随着索引结构的改变,需要新的选种算法来找出每个DNA序列的候选位置。为此,FEM提出了两个选种算法,分别是Group-Seeding算法和Variable-Length算法。在确定候选位置之后,FEM算法采用优化后的Myers算法来验证每一个候选位置。相较于已有的DNA序列比对软件,FEM在内存占用,比对速度,比对精度上均有明显的提升。对于人类基因,可以将16GB大小的哈希索引压缩到3GB,大大减少了内存的使用。此外,相较于BitMapper和Hobbes3这两个最新的DNA序列比对软件,FEM取得了2.8倍和9.3倍的加速比。
论文目录
文章来源
类型: 博士论文
作者: 产院东
导师: 刘卫国
关键词: 生物计算,并行计算,序列比对,众核架构,基因测序
来源: 山东大学
年度: 2019
分类: 基础科学
专业: 生物学
单位: 山东大学
分类号: Q811.4
总页数: 177
文件大小: 13780K
下载量: 195