Next: Finding the best
Up: Comparison of two
Previous: Variable length segments
The segment based techniques described in section 3.1 do
not consider explicitly insertions and deletions. Deletions are often
referred to as ``gaps'', while insertions and deletions are
collectively referred to as ``indels''. Insertions and
deletions are usually needed to align accurately even quite closely
related sequences such as the 
- and 
- globins. The naive approach
to finding the best alignment of two sequences including gaps is to
generate all possible alignments, add up the scores for equivalencing
each amino acid pair in each alignment then select the highest scoring
alignment. However, for two sequences of 100 residues there are 
alternative alignments so such an approach would be time
consuming and infeasible for longer sequences. Fortunately, there is
a group of algorithms that can calculate the best score and alignment
in the order of 
steps. These dynamic programming
algorithms were first developed for protein sequence comparison by
Needleman and Wunsch [13], though similar methods were
independently devised during the late 1960's and early 1970's for use
in the fields of speech processing and computer science
[25].