BLAST

This is the Title of the Book, eMatter Edition

Copyright © 2012 O’Reilly & Associates, Inc. All rights reserved.

Karlin-Altschul Statistics

|

65

Karlin-Altschul Statistics

In 1990, Samuel Karlin and Stephen Altschul published a theory of local alignment

statistics. Karlin-Altschul statistics make five central assumptions:

• A positive score must be possible.

• The expected score must be negative.

• The letters of the sequences are independent and identically distributed (IID).

• The sequences are infinitely long.

• Alignments don’t contain gaps.

The first two assumptions are true for any scoring matrix estimated from real data.

The last three assumptions are problematic because biological sequences have con-

text dependencies, aren’t infinitely long, and are frequently aligned with gaps. You

now know that both alignment and sequence similarity assume independence, and

that this is a necessary convenience. You will soon see how sequence length and gaps

can be accounted for. For now, though, let’s turn to the Karlin-Altschul equation

(see Equation 4-10):

This equation states that the number of alignments expected by chance (E) during a

sequence database search is a function of the size of the search space (m*n), the nor-

malized score (λS), and a minor constant (k).

In a database search, the size of the search space is simply the product of the num-

ber of letters in the query (m) and the number of letters ...