A Dynamic Programming Based Optimal Algorithm for DNA Strand Alignment

摘要

This paper reports on an optimal dynamic programming algorithm for aligning artificially changed DNA Strands. It is based on dynamic algorithm for sequence alignment. This algorithm ensures that the two sequences will be matched optimally. To achieve this, some features including an improved transition constraint, an enhanced scoring system and customized priority assignment are proposed. The constraint gives a new transition path with the existing ones and the other features considers per gap insertion efficiency. The proposed scoring system optimizes the score of the DNA sequences under consideration. The priority scheme is designed to ensure maximum matching. The features are carefully designed through experiments and comparison with the existing ones that prevents insertion of too much gaps to increase the number of matching. The selected criteria increase the number of matches as well as restrict the number of gaps. The proposed algorithm is then extensively subjected to experimental comparison with the established DP-Sequence Aligning Algorithm. This paper reflects that the newly introduced algorithm gives optimum result all the time even compared with the best conventional algorithm.