## Sequence Alignment Algorithms

Algorithms for the pairwise alignment of sequences are the basis for the methods used by modern DNA or protein database search websites. By alignment, we mean pairing up the residues of one sequence with the residues of the other sequence, introducing gaps if necessary, so that the sequences match as closely as possible. For example, the sequences {CATTAGTAG} and {CTAACTTAAG} can be aligned as shown below. This alignment contains 5 matches and 2 mismatches.
 C A T T - A G - - T A G C - - T A A C T T A A G

This website demonstrates two of the most well-known algorithms for pairwise alignment of two sequences:
• Needleman-Wunsch (1970) aligns the two sequences, with gaps, to achieve the greatest number of matches.
• Smith-Waterman (1981) uses a scoring function involving mismatch and gap penalties, and finds the highest-scoring local alignment of subsequences of the two sequences.
The algorithms rely on a mathematical technique called dynamic programming. Essentially, this is based on the principle that to find the best alignment of two sequences containing 10 letters each, we find the best alignment of the first 9 letters of each sequence, and then work out the best way of adding the extra letters. We can thus build up the optimal alignment of two long sequences, by first aligning just the first letters of each (which is an easy problem), then adding more letters one at a time.

Please select the algorithm you want to use, from the list on the left-hand menubar.