OPEN MP-BASED PARALLEL AND SCALABLE GENETIC SEQUENCE ALIGNMENT
Asif Ali Khan*, Laiq Hassan*, Salim Ullah*
ABSTRACT
In bioinformatics, sequence alignment is a common and insistent task. Biologists align genome sequences to find
important similarities and dissimilarities in them. Multiple heuristics and dynamic programming based approaches
are available for sequence alignment. Smith-Waterman (SW), an exact algorithm for local alignment, is the most
accurate of them all. However, the space and time complexity of the SW algorithm is quadratic. It is imperative to
use parallelism and distributed computing techniques in order to speed up this process. In this paper, we discuss and
evaluate an OpenMP based implementation of SW algorithm. All the experiments have been performed on a Linux
based multi-core machine thereby reducing the overall complexity of the SW algorithm from quadratic to linear. The
results obtained with various input sequences demonstrate that the parallel version of the SW algorithm runs 2.63
times faster than its sequential counterpart.
To share on other social networks, click on any share button. What are these?
