Lecture 1.5

Heuristic search

Learning objectives

After this lecture, you should be able to do the following.

Describe how BLAST seeds and extends matches, and predict how the seed rule trades speed against sensitivity.

  1. Describe BLAST’s seed-and-extend idea: find short exact or near word matches first, then extend only the promising ones.
  2. Explain how BLAST breaks the query into short words and also keeps similar words, scored with a substitution matrix, to seed matches.
  3. Predict how a stricter or looser seed rule changes BLAST’s speed and its chance of missing a weak match.
  4. Judge whether an unfamiliar seed design, such as a spaced seed, buys sensitivity without giving up specificity.

Interpret the E-value of a hit, and judge from the numbers whether the hit is a real biological match.

  1. Interpret the E-value of a BLAST hit, including why the same match is less surprising when the database is larger.
  2. Spot when a low E-value is misleading, as it is for a short match between two low-complexity stretches.
  3. Judge whether a BLAST hit is a real biological match by weighing E-value, percent identity, and coverage together.

Explain why searching a database by exhaustive alignment does not scale, why the search looks for local matches, and what has replaced BLAST for large jobs.

  1. Explain that BLAST is an older workhorse and that faster, more sensitive tools have largely replaced it for large jobs.
  2. Explain why a database search looks for local matches, since a query often matches only part of a longer sequence.
  3. Explain why aligning a query against every sequence in a database is too slow, so BLAST trades a guaranteed best answer for speed.

Readings

DEKM §2.5
The short BLAST and FASTA section: heuristic search as seed-and-extend, with the cost argument for why exact search does not scale. Read the BLAST subsection for the seed-and-extend picture. The old runtime estimate against today’s database size is the hook for {lo-why-heuristic-search}. Skim FASTA and skip the score-statistics derivation; you only need the E-value as something to read, not to derive.
(T 1, 9, 10)
BLAST90 §2
The original BLAST method: query words, near-match neighbor words from the substitution matrix, and hit extension. Use the word-list description for {lo-blast-word-matches}. One line of their speed-versus-sensitivity data makes {lo-blast-speed-sensitivity} concrete. The maximal-segment-pair statistics and the long-DNA sections are more than an intro needs.
(T 1, 2, 3, 4)
ISS94 Box 1; low-complexity; Table 1
A practitioner’s tour: reading E-values, the low-complexity trap with a worked case, and the BLAST program family in one table. Box 1 for the plain-language E-value, the low-complexity case for {lo-blast-read-a-hit}. The extreme-value mathematics and the dated network section.
(T 5, 6, 7)

Supplemental

DIAMOND15 abstract and Fig. 1
DIAMOND: a modern protein-search successor, far faster than BLASTX at similar sensitivity. One slide of evidence for {lo-beyond-blast}: the speedup at matched sensitivity is why big jobs no longer use BLAST. The double-indexing and seed-shape internals are out of scope for an intro.
(T 8)
Back to top