Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 49 ยท Sequence Alignment

BLAST and heuristic search

Understand how BLAST searches huge databases fast: seed words, extension, high-scoring pairs, bit scores and E-values, with Python examples and practical interpretation tips.

Smith-Waterman is optimal but slow. A modern protein database holds hundreds of millions of sequences. Running a full dynamic programming matrix between your query and every one of them would take hours or days for a single search. In 1990 Stephen Altschul, Warren Gish, Webb Miller, Eugene Myers and David Lipman published BLAST, the Basic Local Alignment Search Tool, which answers the same question in seconds. It became one of the most cited papers in all of science, and "to BLAST a sequence" is now a verb. This lesson explains how it gains its speed and, more importantly, how to read its statistics.

A query bar above a database bar with three seed hits, one extended into a high-scoring pair, and three step cards
Caption: BLAST finds short exact or near-exact words, extends only the promising ones, and keeps pairs whose score would be rare by chance.

What you will learn

  • The seed-and-extend strategy and why it is fast.
  • What a high-scoring segment pair (HSP) is.
  • How raw scores become bit scores and E-values, and how to interpret them.
  • Which BLAST program to choose and the main pitfalls of reading results.

Key terms

  • Seed (word): a short stretch of the query used to find candidate matches in the database.
  • HSP (high-scoring segment pair): a pair of aligned regions whose score passes the threshold.
  • Bit score (S'): a raw score rescaled so that it can be compared across scoring systems and databases.
  • E-value: the number of hits with at least this score that you expect by chance in a search of this size.
  • Query coverage: the fraction of your query that the alignment covers.

Seed and extend

BLAST is a heuristic: it does not guarantee finding the optimal alignment, but in practice it finds nearly everything worth finding. Its strategy has three stages.

  1. Seeding. The query is cut into short overlapping words. For protein searches, the classic setting uses words of three residues; BLAST also includes "neighborhood" words, which are similar words scoring above a threshold T against a query word under BLOSUM62, so a seed does not have to match exactly. For nucleotide searches, BLASTN's default word size is 11 and the fast MegaBLAST mode uses 28, requiring a longer exact match. The database is scanned for these words using efficient lookup tables.
  2. Extension. Each hit is extended to the left and right along its diagonal, adding the score of each new pair, and stops when the running score falls too far below the best seen (the "X-drop" rule). Later versions (gapped BLAST, 1997) require two non-overlapping hits on the same diagonal within a small window before extending, which saves much work, and then perform a gapped extension around the best.
  3. Evaluation. Extensions that exceed a score cutoff become HSPs. They receive a statistical score, and results are ranked.

The speed comes from not computing most of the matrix: random sequence rarely contains a word hit that extends into something good, so almost all of the database is discarded after the first cheap stage. The price is sensitivity. A distant homolog with no conserved word in common is missed, which is why more sensitive methods (PSI-BLAST, HMMER) exist for remote relationships.

Bit scores and E-values

A raw alignment score depends on the matrix and gap penalties, so a raw score of 100 means different things in different settings. BLAST converts it to a bit score:

Text
S' = (lambda * S - ln K) / ln 2

Here lambda and K are constants of the scoring system, estimated by Karlin-Altschul statistics. For gapped BLASTP with BLOSUM62 and gap costs 11 and 1, typical values are lambda = 0.267 and K = 0.041. The bit score is comparable between searches and increases by one for every doubling of the evidence.

The E-value says how surprising the hit is. With effective query length m and effective database size n:

Text
E = m * n * 2^(-S')

An E-value of 0.001 means you would expect a hit this good by chance once in a thousand searches of a database this size. An E-value of 5 means five such hits are expected by pure chance, so the match is meaningless. The E-value is proportional to database size: the same alignment against a database ten times bigger has an E-value ten times larger, because there are ten times more chances to be fooled, while its bit score is unchanged. For small E-values the p-value is essentially the same: p = 1 - e^(-E).

Common guidelines: E-values below about 1e-5 for protein searches (and 1e-10 or lower for careful work) suggest real homology, values between 0.01 and 1 are grey, and values above 1 are noise. These are conventions, not laws. Short queries have fewer bits to give and never reach tiny E-values even when the match is perfect.

Choosing a program

Program Query Database Use
BLASTN / MegaBLAST nucleotide nucleotide Near-identical sequence; MegaBLAST is fastest
BLASTP protein protein Find protein relatives
BLASTX nucleotide, translated in 6 frames protein Find which protein a DNA read may encode
TBLASTN protein nucleotide, translated Find genes in unannotated DNA
TBLASTX translated translated Distant nucleotide similarity, slow

Protein searches are more sensitive than DNA searches for distant relationships, because the genetic code is degenerate and proteins conserve better than the DNA beneath them. Faster tools such as DIAMOND and MMseqs2 follow the same ideas to search billions of reads against protein databases.

Reading results well

Look at more than the E-value. Query coverage tells you how much of your query matched: an excellent E-value over 10% of the query could be a shared domain. Percent identity over the aligned region helps judge closeness. Check the alignment itself, since low-complexity regions (like runs of one residue) can produce spurious hits, which is why BLAST masks them by default using SEG for proteins and DUST for DNA. The top hit is also not necessarily the closest relative, as databases are uneven: a closely related species may simply not have been sequenced. Finally, remember the database. Results are only as informative as the entries in it, and mislabeled records propagate.

Common misconceptions

  • "BLAST always finds the best alignment." It is a heuristic; Smith-Waterman guarantees the optimum, BLAST approximates it.
  • "A lower E-value always means a better alignment." E-values depend on database size and query length. Compare bit scores across searches.
  • "E-value is a probability." It is an expected count; the probability is p = 1 - e^(-E).
  • "Top hit = species." Do not assign species from one hit without checking coverage, identity and neighboring hits.

Try it

Python Bit score and E-value calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python A toy seed-and-extend search

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python E-value as a function of score and database size

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is BLAST much faster than Smith-Waterman?

    Most of the database is discarded after the cheap word-hit stage.
  2. 2. What does an E-value of 0.001 mean?

    E is the expected number of chance hits with at least that score.
  3. 3. The same alignment is searched against a database ten times bigger. What happens?

    E is proportional to database size; the bit score is independent of it.
  4. 4. Which program finds which protein a DNA read may encode?

    BLASTX translates the nucleotide query in six frames and searches a protein database.
  5. 5. Which is a limitation of seed-and-extend heuristics?

    Without a seed hit, a remote relationship is never extended, so sensitivity is lower than that of dynamic programming.

Summary

  • BLAST finds seeds, extends them (two-hit method, X-drop) and keeps high-scoring segment pairs.
  • Raw scores become bit scores; the E-value is the expected number of chance hits, proportional to database size.
  • Choose BLASTN, BLASTP, BLASTX or TBLASTN by the type of query and database.
  • Read coverage and identity along with E-values, and watch for low-complexity regions and uneven databases.

Next: Multiple sequence alignment