DDGARM: Dotlet Driven Global Alignment with Reduced Matrix

Abstract

Dynamic programming approach provides the most optimal alignment of sequences, but they are known to have high computational cost as well. The approach uses 2-D matrix of size , (m & n being length of the sequences) to compare the sequences and hence the time and space complexity becomes . In this paper we are presenting a global alignment solution which fills only reduced number of diagonals in the 2-D matrix. Dot plot approach which is used for general exploration of sequences is used to identify the minimum amount of diagonals to be filled to get the optimal alignment. DDGARM reduces the memory and execution time significantly compared to the classic dynamic approach suggested by Needleman-Wunsch. Sequences with similar length provided a reduction of up to 90% in the number of cells to be filled and sequences having different length provided reduction up to 75% with no compromise on the alignment quality. Source code is available at: https://sourceforge.net/projects/ddgarm/