Parallel Smith-Waterman Algorithm for DNA sequences Comparison on different cluster architectures

摘要

DNA sequence alignment is one of the most important operations of bioinformatics. In 1981, Smith and Waterman developed a method for sequences local alignment. However, in practice, various heuristics are used due to the processing and memory requirements of Smith and Waterman's algorithm. Even though they are faster, heuristics do not ensure that the optimal alignment is found. For this reason, it is interesting to study how to apply the computer power of different parallel platforms to speed up the sequence alignment process without losing result accuracy. In this paper, a parallelization of Smith-Waterman algorithm is presented using a pipeline scheme due to the data dependencies inherent to the problem. Also, a comparative analysis is carried out regarding the behavior of this algorithm on different multiprocessor architectures: heterogeneous cluster and multicore cluster. Finally, the results obtained with the different tests performed are presented, as well as future research lines.