Coders Packet

Parallel Computing using C++

By Hemkar Goswami

Comparison between the serial and parallel implementation of Smith-Waterman local sequence alignment algorithm using C++(libraries- stdio,stdlib,math and omp).

There have been numerous parallel implementations but very few systems are able to achieve less elapsed time due to parallel overhead time-constraints. As time passes, the world is becoming more and more oriented towards Parallel Computing.

Many of the tasks that were once carried out sequentially are now being carried out in parallel so as to use resources more efficiently and get faster results. Research is being done in Biology with the application Smith-Waterman algorithm it is possible to process and understand nucleic acid/protein sequences. Thus, in this project, we use this inspiration to create something on a smaller scale, but with a large scope.

In the proposed system we use the local alignment of the sequence as the base for the pattern recognition thus getting a better computation time in comparison to the serial operation, our proposed system actively looks for the best possible local alignment of sequences using heavy parallel computing.


The smith-Waterman algorithm calculates the local alignment of two sequences. It produces the best possible local alignment. This includes a substitution matrix and a gap-scoring method. Scores consider a match, mismatch, and substitution.

To measure the comparison between the two sequences, a score be calculated as follows: Given an alignment between sequences S0 and S1, the following values must be assigned, for each column:

                                                                                                                                                                                               ma = (+5) [Match]

                                                                                                                                                                                               mi = (-3) [Mismatch]

                                                                                                                                                                                               G = (-4) [Gap]

Download Complete Code


No comments yet