A Review of Parallel Implementations for the Smith-Waterman Algorithm

Abstract

The rapid advances in sequencing technology have led to an explosion of sequence data. Sequence alignment is the central and fundamental problem in many sequence analysis procedure, while local alignment is often the kernel of these algorithms. Usually, Smith-Waterman algorithm is used to find the best subsequence match between given sequences. However, the high time complexity makes the algorithm time-consuming. A lot of approaches have been developed to accelerate and parallelize it, such as vector-level parallelization, thread-level parallelization, process-level parallelization, and heterogeneous acceleration, but the current researches seem unsystematic, which hinders the further research of parallelizing the algorithm. In this paper, we summarize the current research status of parallel local alignments and describe the data layout in these work. Based on the research status, we emphasize large-scale genomic comparisons. By surveying some typical alignment tools' performance, we discuss some possible directions in the future. We hope our work will provide the developers of the alignment tool with technical principle support, and help researchers choose proper alignment tools.

Keywords: Inter-sequence alignment; Intra-sequence alignment; Smith–Waterman algorithm; Vector-level parallelization.

Fig. 1

Comparison between scalar operation and vector operation

Fig. 2

Distributed and shared memory system model

Fig. 3

Data dependencies in the alignment matrix

Fig. 4

Three intra-sequence alignment approaches

Fig. 5

Sequential layout and striped layout

Fig. 6

Data dependencies of matrix H and E in striped layout

Fig. 7

Data dependencies of the first and last H vectors between the adjacent columns

Fig. 8

Data dependencies of the F vectors on each column

Fig. 9

Inter-sequence alignment

Fig. 10

Blocks of target sequence computed simultaneously