Suppose alignment reveals an intriguing similarity between two sequences. Is the similarity significant or could it have arisen by chance? (We raised this question in Chapter 1.) For some simple phenomena - tossing a coin or rolling dice - it is possible to calculate exactly the expected distribution of results, and the likelihood of any particular result. For sequences it is not trivial to define the population from which the alignment is selected. For instance, to take random strings of nucleotides or amino acids as controls ignores the bias arising from non-random composition.

A practical approach to the problem is as follows: If the score of the alignment observed is no better than might be expected from a random permutation of the sequence, then it is likely to have arisen by chance. We may randomize one of the sequences, many times, realign each result to the second sequence (held fixed), and collect the distribution of resulting scores. Figure 4.4 shows a typical result. For database searches, use the population of results returned from entire database as the population with which to measure the statistics.

Figure 4.4: Optimal local alignment scores for pairs of random amino acid sequences of the same length follow an extreme-value distribution. For any score x, the probability of observing a score ? x is: P(score ? x) = 1 - exp ( - Ke ^{- ?x}), where K and ? are parameters related to...