An Algorithm Based on Fast Walsh Transform for Multiple Sequence Alignment

As a NPproblem, multiple sequence alignment is solved mainly in approximative or heuristic methods, most of which are based on dynamic programming algorithm raised by Smith-Waterman in 1981. In this paper, an alignment method based on fast Walsh transform by the means of Identification of molecular subsequences is brought forward, and it adopts triplet code and subsection strategy. The method increases the differentiation through adding more vectors, it increases the precision and reduces the complexity, and Star-Alignment is introduced to make pair alignment into the alignment. Experiments show the algorithm is effective.