A memory efficient DNA sequence alignment technique using pointing matrix

摘要

A memory efficient approach for pair-wise DNA sequence alignment is presented in this paper. The proposed DNA sequence alignment technique uses a novel concept of pointing matrix. The directed path in the pointing matrix ensures faster and accurate finding of the optimal alignment pertaining with the accuracy ensured by the well known Needleman & Wunsch algorithm. The proposed technique is tested using DNA nucleotides but could use RNA or protein sequences too and it is also suitable for any formal language processing. The complete approach has been simulated considering ten numerous cases (DNA sequence size from 64 to 1024 nucleotides) on 100 pseudo randomly generated DNA sequence pairs in each case. The proposed approach consumes little more time (≈ 9 - 11%) for matrix formation, but it takes 34 - 42% less time to find the optimal alignment compared to the approach based on [2]. For the longer DNA sequences, the space requirement of the proposed approach is significantly lesser compared to the approach based on Needleman-Wunsch [2] though it uses two matrices.