Abstract
In bioinformatics, pair-wise alignment plays a significant role insequence comparison by rating the similarities and distances between protein, DeoxyriboNucleic Acid (DNA), and RiboNucleic Acid (RNA)sequences. Sequence comparison considered as a key stone in building distance matrices. Due to the rapid growth of molecular databases, the need for faster sequence comparison and alignment has become anecessity. High performance computing impacthas increased in the last decade through providing many high performance architectures and tools. In this paper we present a parallel shared memory design for a dynamic programming algorithm named Hash Table-N-Gram-Hirschberg (HT-NGH) an extension of Hashing-N-Gram-Hirschberg (HNGH) and N-Gram-Hirschberg (NGH) algorithm, to speed up the sequence alignment construction process. The focus of the proposed method ison the transformation phase of HT-NGH algorithm since it takes10% of HT-NGH overall run time. The experimental evaluation of the proposed parallel designshows an enhancement in the execution time and speedup without sacrificing the accuracy. However,the decomposition method might slightly slowdown the proposed algorithm due to the differences in performance between the processing units.