A Pairwise Alignment Algorithm for Long Sequences of High Similarity

Alignment algorithms are important in bioinformatics for comparing the similarity among sequences. The algorithm of Needleman–Wunsch is well known for globally aligning two sequences. However, this algorithm is unsuitable for sequences of long length. Many heuristic algorithms are proposed, such as BLAST and FASTA. However, they are still unsuitable for long sequences. In this paper, we study the alignment problem on highly similar sequences. By taking SARS viruses as an example, our result shows that our algorithm runs faster than Clustalx for aligning two SARS viruses. It implies that our algorithm is suitable for viruses of high similarity.