Pairwise alignment for very long nucleic acid sequences

Sequence alignment is one of the fundamental problems in computational biology and has numerous applications. The Smith-Waterman algorithm generates optimal local alignment for pairwise alignment task and has become a standard algorithm in its field. However, the current version of the Smith-Waterman algorithm demands a significant amount of memory and is not suitable for alignment of very long sequences. On the hand, the recent DNA sequencing technologies have produced vast amounts of biological sequences. Some nucleic acid sequences are very long and cannot employ the Smith-Waterman algorithm. To this end, this study proposes the PAAVLS algorithm that follows the dynamic programming technique employed by the Smith-Waterman algorithm and largely reduces the demand of memory. The proposed PAAVLS algorithm can be employed for alignment of very long sequences, i.e., sequences contain more than 100,000,000 nucleotides, on a personal computer. Additionally, the running time of the proposed PAAVLS algorithm is comparable with the running time of the standard Smith-Waterman algorithm.