In Chapters 3 and 5 we saw how to develop an alignment scoring matrix and, given such a matrix, how to find the alignment of two strings with the highest score. In Chapter 6, we learned about some of the large genomic databases available for reference. Perhaps the most commonly performed bioinformatic task is to search a large protein sequence database for entries whose similarity scores may indicate homology with some query sequence, often a newly sequenced protein or putative protein.

The Needleman–Wunsch algorithm described in Chapter 3 constructs global alignments – alignments of the entireties of its two input sequences. In practice, homologous proteins are not similar over their entire lengths. This is because of differences in the importance of different segments of the sequence for the function of the protein. A typical protein has one or more active sites that play crucial roles in the chemical reactions it catalyzes. Acceptance of mutations in the midst of an active site is infrequent, since such mutations are likely to disrupt the protein's function. The segments intervening between the active sites help give the protein its peculiar shape but do not form strong bonds with other molecules as the protein performs its function. Mutations in these regions are more easily tolerated and thus are more common. Hemoglobin provides a good example; it easily tolerates mutations on its outer surface, but mutations affecting the active sites in its interior can destroy its ability to hold the iron-binding heme group essential to its role as oxygen carrier.