Parallel Implementations of Local Sequence Alignment: Hardware and Software - Parallel Computing for Bioinformatics and Computational Biology - page 242

Sequence b

b1 b2 b3 b4 b5

a1

a2

a3

a4

Figure 10.2 Data dependency in Smith-Waterman alignment matrix.

can not be computed in parallel. The only elements on each successive anti-diagonal
(labeled dashed line in Fig. 10.2) are processed in parallel. These data dependen-
cies present a serious challenge for sufficient parallel execution on a general-purpose
parallel processor.

10.3.1 Parallel Computation Approach for Smith-Waterman Algorithm

Database searching applications allow two different granularity alternatives to be
considered: fine-grained and coarse-grained parallelism. Early approaches focused
on data parallel over SIMD machines.

10.3.1.1 Fine-Grain Parallelism Typical dynamic programming-based algo-
rithms, such as Smith-Waterman algorithm, compute an H m , n matrix ( m and m being
the sequence lengths) depending on the three entries H i − 1, j , H i , j − 1 , and H i − 1, j − 1 . Fine
grain means that processors will work together in computing the H matrix, cell by
cell. Some researchers organized the parallel machine as an array of processors to
compute in diagonal-sweep fashion the matrix H (Fig. 10.3). An advantage is that
this strategy only requires local communications in each step. PE i sends H i , j to PE i + 1
to allow it to compute H i + 1, j in the next step, whereas PE i computes H i , j + 1 . Query

Database sequence

b1 b2 b3 b4 b5 b6 …………………………… b n

a1
a2
.
a4
.
.
.
a m

Computation
flow

Working PE

Figure 10.3 Diagonal-sweep fine-grained workload distribution for multiprocessors

machines to avoid data dependencies in Smith-Waterman algorithm.