A novel structure of the Smith-Waterman Algorithm for efficient sequence alignment

摘要

The emergence of bioinformatics has led to many new discoveries in living organisms. These discoveries would not have been possible without the developments made in the sequence alignment techniques. Many sequence alignment algorithms were developed to make the alignment process fast and accurate. However, the more precise algorithms take longer than their less precise counterparts. Researchers came with innovative approaches to combat the time consuming constraint. Their aim was to speed up the computational process by using more efficient implementations of the algorithms using state-of-the-art hardware platforms. Smith Waterman (SW) algorithm, being the most accurate in the alignment process, has been implemented on various high performance computing platforms for the same purpose. However, the intrinsic structure of the algorithm has got little attention. In this paper, we present a novel structure of the SW algorithm that takes less number of cycles at the cost of utilizing a minimal amount of extra hardware resources as compared to its existing form. The newly proposed architecture achieves up to 25% performance gain.