Proposed FPGA-Based hardware architectures for acceleration of Smith-Waterman and K-Mers algorithms

Abstract

In this work, we address the growing challenge of efficiently processing the vast and continuously expanding volume of data in biological databases. The need for fast and accurate sequence analysis techniques is more pressing than ever, given the importance of identifying similarities between biological sequences for applications in genomics, taxonomy, and beyond. Central to this effort is optimizing sequence alignment algorithms, particularly the Smith-Waterman (SW), a high-precision method based on dynamic programming, and K-Mers, a technique for counting subsequences fundamental in genomic analysis. We propose an innovative parallel hardware architecture for the SW algorithm, incorporating a systolic array structure that significantly accelerates the forward and backward phases of alignment. This architecture pre-organizes the alignment in the forward stage, reducing the complexity of the subsequent backtracking initiated from the maximum score position. Validated on Field-Programmable Gate Array (FPGA), the architecture achieved a rate of up to 79.5 Giga Cell Updates per Second (GCPUS), demonstrating a notable advancement in processing efficiency. Additionally, we developed a K-Mers based algorithm focused on the exact extraction of short subsequences, characterized by its low memory consumption, feasibility of execution time, high parallelization capability, and energy efficiency. Primarily intended for use in FPGA, the algorithm is also adaptable to other hardware platforms. These contributions not only set new standards in speed and efficiency for the processing of biological data but also pave the way for significant advances in genomic and taxonomic research, among other areas of bioinformatics.