Jan 192012

The Smith–Waterman algorithm is a well-known algorithm for performing local sequence alignment for determining similar regions between two nucleotide or protein sequences. Proteins are made by aminoacid sequences and similar protein structure has similar aminoacid sequence.In this project we did the parallel implementation of the Smith-Waterman Algorithm using Message Passing Interface code.

To compare two aminoacid sequence, initially we have to align the sequences to compare them. To find the best alignment between two sequences the algorithm initially populates a matrix H of size N × N (N is size of sequence) using a scoring criteria. It requires a scoring matrix (cost of matching of two symbols) and a gap penalty for mismatch of two symbols. After populating the matrix H we can obtain the optimum local alignment by tracking back the matrix starting with the highest value in the matrix.

Pipelined computation to achieve specific degree of parallelism was used Also different parallelizing techniques to find optimum parallelization technique for the problem were compared. Parallelizing was started using different blocking sizes B at the column level. Furthermore, parallelization using different levels of interleave I at the row level was introduces.

For performance measurement the performance model of both the implementations for two interconnection networks was created which are linear and 2D-Mesh interconnection network.

All the details coud be found here.