Online Lectures on Bioinformatics
Alignment statistics
The Karlin-Altschul formula
The database search tool BLAST (Basic local alignment search tool) finds all segment pairs of the query and the sequences of the searched database, whose scores can not be improved by extension or trimming. These segment pairs are denoted as highest scoring segment pairs (HSP).
Assuming a random distribution of the maximum score of the HSPs and
considering that the exceedance of a threshold t by the this
maximum score is a rare event, one could model the probability
of such exceedances by a Poisson distribution:
is the mean value of the ditribution and k is the
frequency of exceedances.
Thus the probability for the exceedance of the threshold t by the
best HSP is
Karlin and Altschul [KA90] give the following formula
to compute the probability for the score H(a,b) of the best HSP to
exceed a threshold t:
The expression
is interpreted as the mean value
of the Poisson distribution:
On the average
HSP exceed t and
depends on the sequence lengths n,m, on p, which is
calculated directly, and on 
, which is obtained numerically.
exercises
Comments are very welcome.
luz@molgen.mpg.de