Development and hardware acceleration of a novel ۲-D BWA-MEM DNA sequencing alignment algorithm

Day by day progress in Next-Generation Sequencing (NGS) is enabling generation of DNA sequence data at ever faster rates and at low cost which means a dramatic increase at the amounts of data being sequenced, Nowadays, sequencing nearly ۲۰ billion reads (short DNA fragments) costs about ۱۰۰۰ dollars per human genome and sequencers can generate ۶ Tera bases of data in less than two days. At this article, we considered the seed extension kernel of the Burrows-Wheeler Alignment (BWA) genomic mapping algorithm for accelerating with FPGA devices. We have proposed an FPGA-based accelerated implementation for the seed extension kernel. The Smith-Waterman algorithm is used during the seed extension to find the optimum alignment between two sequences. The state-of-the-art architectures use ۱D-systolic arrays to fill a similarity matrix, based on the best score out of all match combinations, mismatches and gaps are computed. The cells on the same anti-diagonal are calculated in parallel in these architectures. We propose a novel ۲-dimensional architecture in which all the cells on the same row and the same column are computed in parallel and, thereby, significantly speed up the process. Our simulation results show that the proposed architecture can work with up-to ۳۱۲ MHz frequency in Synopsys Design Compiler for ۱۸۰-nm CMOS technology and be up to ۵۷۰× and ۱.۴× faster than the software execution and the ۱D-systolic arrays, respectively.

Keywords:

Bioinformatics , FPGA , Smith-Waterman