Optimizing Runtime Memory Size of Smith-Waterman Algorithm for Long Sequences Alignment

Sequence alignment is used to help researchers see areas of similarity between two sequences. Hence, it is a key component of many applications, such as DNA matching, plagiarism detection, and spelling correction. The Smith-Waterman algorithm (SWA) is widely used to calculate the sequence alignment because it is guaranteed to find an optimal solution. This algorithm creates a matrix of the size n * m where the symbols n, m refers to the lengths of two sequences needed to be aligned. Therefore, it requires impersonal hardware with a large amount of main memory at runtime to align long sequences. Furthermore, it may be impractical if the length of some sequences exceeds the memory requirements for low-resource devices. This research redesigned the Smith-Waterman algorithm to be implemented without creating the matrix of the size n * m. Experimental results show that the proposed algorithm outperformed the SWA algorithm in terms of memory size and processing time while maintaining accuracy. The percentage decreases in terms of memory size and processing time were up to 88.28% and up to 66% respectively. The proposed algorithm is hoped to contribute to various applications that initially require low memory consumption, such as applications of personal laptops, smartphones, and tablets.