An Improved Longest Common Subsequence Algorithm for Reducing Memory Complexity in Global Alignment of DNA Sequences

The comparison of biological sequences is one of the oldest problems in computational biology. Global alignment is designed to search for highly similar regions in two DNA sequences, where appear in the same order and orientation. Longest Common Subsequence (LCS) is the most typical algorithm for global alignment that has optimal solution and independent to the shape of its input sequences. Since the space complexity of this algorithm is the multiplication of sequence lengths; we cannot use it for long sequences. In this paper, some rules are extracted to reduce amount of redundant information. Remained information is stacked to be used in backward iteration for finding the optimal path. As we examined in the proposed algorithm, the stack size in comparison with space consumed by LCS algorithm is reduced about 10 times and we could increase the length of input DNA sequences in global alignment.