马毅超 张晓盼 王鑫

（陕西科技大学电子信息与人工智能学院 陕西省西安市 710021）

1 引言

序列对比[1]是指将测序仪单次测序所得到的长度较短的碱基序列（reads）映射到参考基因组上的过程。序列对比经常被用于分析序列片段的相似性，通过对比结果得出物种之间的同源性及其生物学特征，以此来判断生物的健康状况以及进化信息等。近年来，生物学数据库中的序列数据呈现爆炸式增长，以美国国家生物技术信息中心(NationalCenterforBiotechnologyInformation，NCBI)建立的DNA 序列数据库GenBank 为例，DNA、RNA 和蛋白质的序列数据大约每6 个月就会翻一番[2]。新一代测序技术也将产生海量的测序数据序列（reads），生物信息学将面临着对这些海量数据处理的严峻挑战。因此，通过研究序列对比问题可以加快对数据的处理速度，从而应对生物信息学对大量数据研究的需求。

M.Burrows and D.J.Wheeler 于1994年提出了BWT 算法[3]，该思想首先被用于数据的压缩算法[4]，之后逐渐被应用于字符串的匹配。BWT 算法于2007年首次应用于DNA 序列对比问题中，2009年以后普遍用于将DNA 短序列映射到参考基因组。如Bowtie，BWA，SOAP2等主流的序列对比软件都采用了BWT技术[2]，但是BWT 算法运算量大，当数据规模较大时，从参考基因组中查找短序列reads 的时间较长。因此，本文提出了一种基于HLS 的并行方法对BWT 算法进行加速。

2 Vivado High-level Synthesis介绍

Xilinx 公司推出的Vivado High-Level Synthesis (HLS)工具[5]可以将C 或者C++规范转换为寄存器传输级（RTL）实现，并将其合成为现场可编程门阵列（FPGA）。FPGA 则提供了一中大规模的并行架构，它在性能、成本和功率方面优于传统处理器。……