Background: Sequence comparison and alignment plays an important role in computational biology as they allow for rating the similarities between molecular sequences. Pair-wise alignment contributes significantly in calculating the similarity between sequences by constructing the optimal alignment. The Hash Table-N-Gram-Hirschberg (HT-NGH) algorithm, which is an extension to the Hashing-N-Gram-Hirschberg (HNGH) and N-Gram-Hirschberg (NGH) algorithms, represents a pair-wise alignment method that uses the capabilities of the hash table technique for the purpose of building the alignment. Due to the current technology, molecular databases have exponentially grown to highlight the needs for faster and efficient methods that can handle these amounts of data. On the other hand, the present technology provides a verity of high performance architectures and tools.
Results: This paper presents a parallel shared memory algorithm for protein pair-wise alignment method, namely, the HT-NGH algorithm in order to enhance the time performance of sequences’ comparisons and alignments. The proposed parallel algorithm targets the transformation phase of the HT-NGH algorithm since it consumes about 10% of alignment’s executional time. Datasets are decomposed up to sequence level for a more efficient utilization of processing units (no idle processing unit).
Conclusions: As a result, the proposed algorithm demonstrates a significant improvement in terms of time performance without sacrificing accuracy. The speed up pertaining to the parallel algorithm reaches 2.08, 2.88, and 3.87 when using 2, 3, and 4 cores, respectively. Furthermore, this algorithm gains high efficiency as it reaches 1.04, 0.96, and 0.97 when using 2, 3, and 4 cores, respectively.