DNA Sequence Alignment: Exploring All Potential Optimal Solutions

This paper presents a DNA Sequence Alignment approach that explores all potential optimal solutions for aligning pairwise DNA sequences. The suggested DNA sequence alignment technique introduces a new concept of the Direction matrix to explore all the possible DNA sequence alignments by traversing the specified directions within the matrix. The directions are symbolized by symbols "d" ( for diagonal), "u" (for upwards), and "l" (for left). The presence of these symbols symbolizes the path that should be traversed within the Direction matrix to generate the paired sequence alignments. The proposed method has been fully experimented across six distinct cases, with sequence lengths ranging from 8 to 64 nucleotides, using 100 pairs of pseudo randomly generated sequences. Although, the proposed method takes longer alignment time as compared to the well-established Needleman & Wunsch algorithm, but is more efficient as it generates all possible optimal sequence alignments instead only one.