The improvement and implementation on the algorithm for local alignment of pairs of DNA sequences

摘要

This paper improves the Smith-Waterman algorithm. On the one hand, it present the two-character alignment, improve the scoring function and scoring matrix to enhance the specificity and reduce the randomness of the matching sequences. On the other hand, changing the score matrix overall storage to two-line storage drastically reduces the complexity of the program space. Finally, using the Python language achieves the improved algorithm, and experiment with simulated data which is randomly generated. When the length of DNA sequences is less than 3KB, the improve algorithm is more effective because of the Identity and Similarity of the improve algorithm are much higher than the Smith-Waterman algorithm.