Database searching with BLAST

Concept

Database searching with BLAST

T-107Home BU-401Threads information · systems

Statement

Fast approximate matching against large databases.

Why it matters

sequence-alignment establishes dynamic programming as the exact, guaranteed-optimal method for aligning two sequences, but that guarantee comes at a computational cost — roughly proportional to the product of the two sequences' lengths — that becomes completely impractical once a query must be compared against every one of many millions of sequences in a modern database. BLAST is the standard practical answer: a heuristic that abandons the guarantee of finding the single best possible alignment in exchange for a dramatic, database-scale speed-up, making routine tasks such as identifying an unknown gene, finding homologous sequences across species, or annotating a newly sequenced genome computationally feasible at all.

Nearly every later step in a typical bioinformatics workflow — building a multiple alignment, constructing a phylogenetic-tree-construction, or interpreting a hidden-markov-models-based gene model — routinely begins with a BLAST search used to first identify a relevant, manageable set of candidate homologous sequences out of an otherwise enormous database.

Hypotheses

A genuine local homology between query and database sequence contains, with high probability, at least one short exact-matching subsequence (a "word" or "seed").This is the empirical justification for skipping full alignment computation entirely for the vast majority of database sequences: true evolutionary relationship generally implies stretches of strong local conservation, particularly around functionally important residues, and a sufficiently short word is likely to coincide exactly somewhere within any biologically real match — whereas the enormous number of unrelated sequences overwhelmingly will not share even one such short exact word by chance. The scoring scheme used to extend and rank candidate alignments (a substitution matrix such as BLOSUM or PAM, together with gap penalties) reflects genuine evolutionary substitution likelihoods.Without a biologically meaningful scoring scheme, a higher alignment score would carry no particular evidential weight toward true homology versus chance similarity; the statistical framework in Step 5 depends on this scoring scheme's properties to translate a raw score into a calibrated significance value. The statistical significance calculation (Step 5) assumes the database's sequence composition and length are representative of the search space being tested; searching a small or compositionally unusual database can distort E-values relative to a search of a larger, more typical one.

Proof

\text{Decompose the query into overlapping words of fixed length } W \text{ (typically } W{=}11 \text{ nucleotide, } W{=}3\text{ protein)}

Rather than comparing the full query against a full database sequence directly, BLAST first breaks the query into every overlapping short subsequence of length \(W\) — the seeding step, and the source of BLAST's fundamental speed advantage over exhaustive dynamic programming. A

\text{Look up each query word against a precomputed index of the database, retaining only positions with an exact (or, for protein, sufficiently high-scoring) word match}

By Hypotheses, a genuine local homology is very likely to contain at least one exactly (or near-exactly) matching word; scanning only these candidate "hit" positions, rather than every possible alignment offset against every database sequence, is what reduces the search from a cost scaling with the full database size times full sequence length to something far smaller in practice. A

\text{Extend each seed hit in both directions, accumulating a running alignment score, stopping once the score falls a fixed amount below its running maximum}

This greedy, local extension around a promising seed (not a global search over the entire sequence) produces a High-scoring Segment Pair (HSP): a locally optimal ungapped or gapped alignment anchored at that seed. The drop-off (X-drop) stopping rule keeps this extension step itself fast, at some risk of prematurely abandoning an extension that would have recovered a higher score slightly further along. A

\text{Retain only HSPs whose score exceeds a minimum reporting threshold}

The overwhelming majority of seed hits extend into only weak, short alignments and are discarded at this stage; only a small fraction survive as HSPs worth statistically evaluating, which is what keeps the number of results returned to a user manageable even against a database of millions of sequences. A

E = K m n\, e^{-\lambda S}

Karlin-Altschul statistics model the distribution of best local-alignment scores expected from purely random, unrelated sequences as an extreme-value distribution; \(m\) and \(n\) are the query and database lengths (or total database size), \(S\) is the HSP's raw score, and \(K,\lambda\) are scale/shape parameters fitted to the scoring scheme. The resulting E-value gives the expected number of unrelated alignments scoring at least \(S\) that would occur by chance alone in a database of that size — a smaller E-value indicates a score far less likely to have arisen by chance, and hence stronger statistical evidence of true homology. B

Result

\text{Seed (exact short word)} \ \to\ \text{Extend (greedy local alignment)} \ \to\ \text{Evaluate (E-value / bit score)}

Reading. BLAST approximates the exhaustive dynamic-programming search of sequence-alignment by restricting genuinely full alignment computation to only the small number of regions anchored by an exact short-word seed match, then assigns each surviving candidate alignment a rigorously calibrated statistical significance rather than relying on the raw score alone.

Scope. Effective and fast for finding regions of reasonably strong local similarity across large databases; because it depends on at least one exact seed word being present (Hypotheses), it can in principle miss true but short, weak, or highly diverged homologs that happen to contain no such exact match anywhere in their length.

Corollaries & converses

sequence-alignment's exact dynamic-programming methods are not abandoned by BLAST but are instead applied locally, within Step 3's extension around each seed — BLAST is best understood as making full alignment tractable at database scale by restricting where it is applied, not as a wholesale replacement for it.
hidden-markov-models-based profile search offers a complementary approach to homology detection, generally more sensitive to weak or highly diverged similarity than a single-sequence BLAST search, at the cost of greater computational expense — a standard follow-up when a BLAST search returns no significant hits but true remote homology is still suspected.
Converse: a very low E-value for a given HSP, on its own, establishes only that the observed alignment score is highly unlikely to have arisen from chance similarity between unrelated sequences; it does not, by itself, establish that the two sequences share the same specific biological function, which requires additional evidence (Discussion's common misconception).

Fails without

Drop the seed-existence assumption: a real but highly diverged homology containing no exact-matching short word anywhere in either sequence will simply never be found by the seed-and-extend heuristic, however statistically significant the true alignment actually is — the acknowledged trade-off against slower, exhaustive dynamic-programming alignment (sequence-alignment), which is guaranteed to find it.
Use a scoring matrix mismatched to the sequences' true evolutionary divergence (e.g. a matrix tuned for close relatives applied to highly diverged sequences): the statistical calibration underlying E-value and bit-score interpretation no longer holds, and reported significance values become an unreliable guide to genuine homology.

Common errors

Interpreting the E-value as a probability that must lie between \(0\) and \(1\); it is instead an expected count of chance matches, and can in principle exceed \(1\) for weak, statistically unremarkable alignments.
Assuming BLAST performs an exhaustive, guaranteed-optimal search of the kind sequence-alignment's dynamic programming provides; it is a heuristic (Hypotheses) that can, in principle, miss a true but weak or short homology containing no matching seed word.
Comparing raw alignment scores directly across two different searches run against databases of different sizes, rather than comparing E-values (which explicitly incorporate database size, Step 5) or bit scores (which are already normalised).
Treating a statistically significant BLAST hit as automatic proof of shared biological function, rather than as evidence of statistically improbable sequence similarity that still requires further corroboration (Corollaries' Converse).

Discussion

BLAST (Basic Local Alignment Search Tool) was introduced by Stephen Altschul, Warren Gish, Webb Miller, Eugene Myers and David Lipman in 1990, explicitly engineered for the speed needed as sequence databases began growing far too large for exhaustive dynamic-programming search of every entry; a later, gapped version published in 1997 extended the original ungapped seed-and-extend algorithm to permit insertions and deletions within an HSP, considerably closer in flexibility to full Smith-Waterman-style local alignment while retaining the original seed-based speed advantage.

Different BLAST variants (BLASTN for nucleotide-nucleotide, BLASTP for protein-protein, BLASTX for translated-nucleotide-against-protein, and others) apply the identical seed-extend-evaluate framework developed here with different word lengths, scoring schemes, and translation steps suited to the specific sequence types being compared, rather than representing fundamentally different algorithms.

Common misconception: that a "BLAST hit" is synonymous with "homolog." As the Corollaries' converse notes, a significant E-value is strong statistical evidence against chance similarity but is not, by itself, definitive proof of evolutionary relationship or shared function — particularly for hits near the significance threshold, where corroborating evidence (reciprocal best hit, phylogenetic placement via phylogenetic-tree-construction, conserved functional motifs) is standard practice before drawing a firm conclusion.

Worked examples

\text{Query length } m = 300\text{ residues}; \quad \text{Database size } n = 5\times10^{8}\text{ residues}; \quad \text{HSP score } S \text{ gives bit score } S' = 45

The bit score \(S'\) is a normalised score (incorporating \(K\) and \(\lambda\) from Step 5) that no longer depends on the specific scoring matrix used, making it directly comparable across different searches; the E-value, by contrast, still depends explicitly on the search space size \(mn\). A

E \approx mn\cdot 2^{-S'}

A standard simplified relationship between bit score and E-value (dropping the constant prefactor \(K\) for illustration): the same bit score \(S'=45\) yields a far smaller (more significant) E-value against a smaller, more targeted database than against the full \(5\times10^8\)-residue database used here, directly illustrating why E-values, unlike bit scores, are not comparable across differently sized databases (Common errors). B

\text{Bit score is database-independent; E-value scales directly with database size } mn

Reading. The same underlying alignment quality is reported as a fixed bit score regardless of database size, but translates into a different E-value depending on exactly how large a "haystack" the "needle" was found in — searching a larger database makes any given score somewhat less individually surprising, purely as a matter of search-space size.

Scope. This is why bit score, not E-value, is the preferred quantity for comparing hit quality across searches run against different databases or database versions.

Problems

Explain why doubling the size of the database searched, with the HSP score held fixed, roughly doubles the reported E-value for that HSP, using Step 5.
Solution
Step 5 gives \(E=Kmn\,e^{-\lambda S}\), which is directly proportional to \(n\) (database size) at fixed \(m\), \(S\), \(K\), and \(\lambda\). Doubling \(n\) therefore doubles \(E\) exactly, reflecting that the same alignment score is twice as likely to be matched by chance somewhere within a database twice as large.
Two HSPs from the same search have E-values of \(10^{-50}\) and \(0.2\) respectively. Which, if either, is more likely to represent genuine homology, and why does the second E-value not necessarily mean "no relationship"?
Solution
The HSP with \(E=10^{-50}\) is overwhelming statistical evidence of true homology, since a chance match of that quality is expected essentially never in a database of realistic size. \(E=0.2\) means roughly \(0.2\) such alignments are expected purely by chance in a database this size — not negligible, but also not necessarily meaningless; some genuine, especially short or weakly conserved, homologs do score in this marginal range, so an E-value around \(0.2\) is inconclusive on its own and would need corroborating evidence (Corollaries' Converse), not automatic dismissal.
A search using word length \(W=11\) (typical nucleotide default) fails to detect a true but highly diverged homology, while lowering \(W\) to \(7\) detects it successfully. Explain this outcome using the Hypotheses and Result's Scope.
Solution
Detection depends on the query and the true homolog sharing at least one exactly matching word of the chosen length (Hypotheses). A highly diverged homolog may have accumulated enough substitutions that no \(11\)-letter exact match remains anywhere between the two sequences, causing BLAST to miss the seed entirely (Result, Scope, "can in principle miss...diverged homologs"). A shorter word length of \(7\) is more likely to find at least one exactly matching short stretch by chance, at the cost of also generating many more spurious seed hits to filter through during Steps 2–4 — the standard sensitivity/speed trade-off in choosing \(W\).