Dataflow Acceleration of Smith-Waterman with Traceback for High Throughput Next Generation Sequencing
Konstantina Koliogeorgi, Nils Voss, Sotiria Fytraki, Sotirios Xydis, Georgi Gaydadjiev, Dimitrios Soudris · 2019
Smith-Waterman algorithm is widely adopted by most popular DNA sequence aligners. The inherent algorithm computational intensity and the vast amount of NGS input data it operates on, create a bottleneck in genomic analysis flows for short-read alignment. FPGA architectures have been extensively leveraged to alleviate the problem, each one adopting a different approach. In existing solutions, effective co-design of the NGS short-read alignment still remains an open issue, mainly due to narrow view on real integration aspects, such as system wide communication and accelerator call overheads. In this paper, we propose a dataflow architecture for Smith-Waterman Matrix-fill and Traceback alignment stages, to perform short-read alignment on NGS data. The architectural decision of moving both stages on chip extinguishes the communication overhead, and coupled with radical software restructuring, allows for efficient integration into widely-used Bowtie2 aligner. This approach delivers x18 speedup over the respective Bowtie2 standalone components, while our co-designed Bowtie2 demonstrates a 35% boost in performance.