Algorighmic Research On Global Pairwise Alignments Based On Dynamic Programming

Sequence alignment is a fundamental task for bioinformatica research. Most of sequence alignment software utilize dynamic programming (DP) or the hidden Markov Model (HMM) as the core algorithm for gap open and extension. However, a general problem is that although a majority of the currently available alignments provide optimal or near optimal results, they are greatly limited by the bottleneck of low computation speed induced by the high computation complexity. In recent years, it is due to the modification and improvement of the algorithms and especially the development of computer science and technology both in hardware and software that lead to the advent of such practical analytic tools as Blast, FASTA,CLUSTALW, which can relatively cater for the need of research in both efficiency and accuracy. The fundamental way to improve computation efficiency and accuracy is to better the alignment algorithms in principle so as to minish the computation complexity. As more and more genome sequencing projects are accomplished one after another, the amount of sequence data has been exponentially increased, the demand for efficient alignment algorithm in sequence analysis is increasingly urgent.Based on the concept of sequence segmentation, we applied the multiple-stage dynamic programming algorithm in pairwise alignment to devise a new algorithm named SAMIDP and developed the corresponding programs in VisualBASIC, we find that SAMIDP not only reduces the computation complexity to O(N), but also obtains even satisfactory accuracy, and it is expected that the new algorithm will be important in global sequence alignment.