Sequence alignment algorithms have been developed and popularly used in bioinformatics.
multiple sequence alignment (MSA) has been shown to be NP complete (Wang and Jiang, 1994) and various heuristic algorithms have been proposed to solve this problem (Notredame, 2002).