摘 要

序列比对是高通量数据分析中重要的一环，而近年来随着测序的成本进一步下降，产生的测序数据也越来越多，原有的测序软件已经无法很好的满足现在的分析需求。云计算的发展使得高通量数据分析可以按需获取计算能力，在此基础上提升序列比对速度就能进一步的降低数据分析成本。本文的主要内容如下：

1）以现在使用最广泛的序列比对软件BWA（Burrows-Wheeler Alignment tool）为例，分析了序列比对问题的关键数据结构和算法。

2）通过性能分析工具分析了BWA软件的性能指标，找到了性能瓶颈的原因。

3）使用AVX（Advanced Vector Extensions）改进了BWA软件，并在性能上取得了一定的提高。

关键词：序列比对；性能优化；BWA；

Abstract

Sequence alignment is an important step for NGS(Next-generation sequencing) data analysis. in recent years, with a further decline in the cost of sequencing, sequencing data generated by more and more, and the sequence alignment proposed new performance requirements. Cloud computing let we can get the computing power as much as we needed in NGS data analysis. We can further reduce the cost of sequencing data analysis by improving the speed of sequence alignment. The main contents are as follows:

1) Take the most widely used sequence alignment software BWA(Burrows-Wheeler Alignment tool) as an example to show main data structures and algorithms for sequence alignment.

2) Analysis of the performance of BWA software, then found the causes of performance bottlenecks.

3) Improved the speed of sequence alignment software BWA by using AVX(Advanced Vector Extensions)

Key Words：sequence alignment; performance optimal; BWA;

目录

摘要 I

Abstract II

第1章 绪论 1

1.1 课题研究的背景与意义 1

1.2 课题研究内容 2

1.3 论文的组织结构 2

第2章 序列比对 3

2.1 序列比对问题描述 3

2.2 前缀树和字符串匹配 3

2.3 基于块排序压缩的后缀数组 4

2.4 后缀数组区间 5

2.5 通过反向搜索进行精确匹配 6

2.6 通过遍历边界和回溯进行模糊匹配 6

2.7 序列比对过程 8

2.8 本章小节 9

第3章 BWA性能分析 10

3.1 性能分析工具与运行环境 10

3.2 硬件事件和性能监控单元 11

3.3 扩展性能分析 11

3.4 负载不平衡 12

3.5 序列长度与指令数的关系 13

3.6 热点分析 15

3.7 本章小结 16

第4章 性能优化 17

4.1 向量化 17

4.2 语句优化 17

4.3 优化结果 18

4.4本章小节 19

第5章 总结与展望 20

5.1 总结 20

5.2 待探究的问题 20

参考文献 22

致谢 23

第1章 绪论

1.1 课题研究的背景与意义

随着高通量测序技术的发展对生物医学研究产生了重大影响，使得生物医学研究从试验驱动转变为数据驱动，然而海量的数据分析任务也为高通量技术广泛应用带来了新的挑战。^[1][2]一台高通量测序仪一次运行可以测量600个人的全基因组信息，数据量达到1.8TB。目前常用的数据分析软件在八核CPU（Central Processing Unit）的服务器上处理这些数据需要10天左右的时间，无法满足实际应用需求。

由于散热技术和硬件生产技术无法满足提高处理器频率对功耗的设计要求，现代处理器的频率近似停滞。处理器硬件生产商主要通过多核^[3]和向量化^[4~5]等技术来提高处理器的性能。多核技术是采用在同一个芯片上集成多个核心的解决方案来提升CPU的处理性能。多核CPU的核相互独立，每一个核有独立的硬件单元，可以同时执行多条指令。^[6]向量化技术指的是增加寄存器的宽度和指令的宽度来同时处理多个数据。多核和向量化技术的出现提升了处理器的执行能力。通过稍微降低频率，现在的散热技术能够满足处理器对功耗的需求。绝大多数现代处理器，如X86多核CPU、ARM（Advanced RISC Machine）多核CPU、GPU（Graphics Processing Unit）及DSP（Digital Signal Processor）等，都已经采用了多核技术和向量化技术。^[7]多核和向量化的出现满足了应用对计算能力的需求。

虽然现代多核CPU都具有256位以上的指令宽度并利用流水线技术^[8]在底层的指令上实现了并行，但是传统的高通量测序分析软件无法充分的利用指令宽度以及多核资源^[9]。OpenMP（Open Multi-Processing） ^[10~12]是一套适用于多核处理器的编程接口，旨在简化并行程序的开发。使用OpenMP开发并行程序无需关心线程的分配、同步、管理、调度、负载平衡等诸多并行化的细节问题^[13]。使用OpenMP开发的并行程序在不支持OpenMP的平台上也能简单的转换成串行程序执行，具有良好的可移植性。^[14]AVX2（Advanced Vector Extensions 2）是Intel在Haswell架构之后引入的对于SSE^[15]（Streaming SIMD Extensions）和AVX的扩充向量化指令集，可以通过其提供C/C 编程接口方便的实现SIMD（Single Instruction Multiple Data）达到数据并行，充分的利用现代CPU的指令宽度来提升程序的运行效率。

我们研究的目标是充分利用CPU多核和向量化的特点对高通量数据分析软件进行优化，这对于提高高通量数据分析软件的处理效率挖掘出更多有价值的分析结果具有重大意义。