Multiple Sequence Alignment

The multiple sequence alignment (MA) plays an important role in sequence analysis. However, it has been proven to be an NP-hard problem. This means the computation complexity of MSA increases exponentially with the number of sequences. The presented algorithms are mostly heuristic and many of them are based on pairwise sequence alignment. Hence we begin with pairwise alignment of multiple sequences and discuss the topological space induced by pairwise alignment of multiple sequences, since different optimization criteria may lead to different results. We discuss several optimization indices here: the sum of pairs (SP); Shannon entropy; similarity rate and the rate of virtual symbols. Based on this discussion, we present a new multiple sequence alignment based on SPA called super multiple sequence alignment (SMA). We give a detailed description of the algorithm and compare it to some popular MA algorithms and find that it works well enough, especially with respect to speed. An example of SARS multiple sequence alignment is given at the end of this chapter.