Proposal of Smith-Waterman algorithm on FPGA to accelerate the forward and backtracking steps

Area of Science:

• Bioinformatics
• Computational Biology
• Hardware Acceleration

Background:

• Sequence alignment is crucial in bioinformatics for identifying similarities in biological data.
• The Smith-Waterman (SW) algorithm offers high precision but faces challenges with massive, exponentially growing biological databases.
• High-speed data processing is essential for efficient analysis of large-scale biological sequence data.

Purpose of the Study:

• To propose a parallel hardware design for the SW algorithm to accelerate sequence alignment.
• To enhance the processing speed of both the forward and backtracking stages of the SW algorithm.
• To reduce the computational complexity associated with sequence alignment in bioinformatics.

Main Methods:

• A parallel hardware design utilizing a systolic array structure for the SW algorithm.
• Implementation of a strategy to calculate and store paths during the forward stage to simplify backtracking.
• Validation of the architecture on a Field-Programmable Gate Array (FPGA).

Main Results:

• The proposed design accelerates both the forward and backtracking steps of the SW algorithm.
• Pre-organizing alignment paths in the forward stage reduces backtracking complexity.
• Achieved a processing speed of up to 79.5 Giga Cell Updates per Second (GCPUS) on FPGA.

Conclusions:

• The developed parallel hardware design offers a significant speedup for SW sequence alignment.
• This approach is effective for handling large-volume biological data, addressing current bioinformatics challenges.
• The FPGA implementation demonstrates the practical viability and high performance of the proposed architecture.