Parallelisation of sequence comparison algorithms using hybridised parallel techniques

摘要

The aim of this work is how to speed up the process of the biological (DNA and proteins) sequence comparison process by using a hybrid parallelisation technique of combining different parallel methods. Smith-Waterman algorithm has been known as the most optimal algorithm for doing the sequence comparison. Unfortunately, this algorithm is considered slow due to its quadratic time complexity. Multiple Instruction Multiple Data (MIMD), Single Instruction Multiple Data (SIMD), and Single Program Multiple Data (SPMD) methods were chosen because of their efficiency, wide-availability in off-the-shelf inexpensive machines and simple network distributed systems. Based on the results, the combined (hybrid) algorithm has succeeded in reducing the overall algorithm execution time.