Describe BLAST and homology searching — Biology notes

WHAT is homology searching?

WHY not just line sequences up perfectly? (The problem BLAST solves)

A full optimal alignment of two sequences (the Smith–Waterman algorithm) costs about $O(mn)$ time for lengths $m$ and $n$ . Comparing your query against a database of size $N$ letters costs $O(m\cdot N)$ — with $N$ in the billions, that is far too slow.

HOW BLAST works — step by step

Figure — Describe BLAST and homology searching

Step 1 — Break the query into words (k-mers). The query is chopped into overlapping words of length == $w$ == (default $w=3$ for proteins, $w=11$ for DNA). Why this step? Words are the small anchors we can look up instantly in a pre-built index.

Step 2 — Build a neighborhood of similar words. For each query word, list all words scoring $\geq T$ (threshold) against it using a substitution matrix (e.g. BLOSUM62). So the word PQG also generates near-neighbours like PEG, PKG. Why this step? Homologs have substitutions, not just identities — allowing scored neighbours catches distant relatives.

Step 3 — Scan the database for exact hits to any neighbourhood word (seeds). Why this step? Any database position matching a neighbourhood word is a promising place to start.

Step 4 — Extend each seed both directions (ungapped, then gapped). Keep extending while the running score rises; stop and trim back once it drops by more than a set amount (X-drop). This produces a High-scoring Segment Pair (HSP). Why this step? We only spend effort near real matches, not on random regions.

Step 5 — Score the alignment. $S = \sum_{\text{aligned pairs}} s(a_i, b_i) \;-\; (\text{gap penalties})$ where $s(a,b)$ comes from the substitution matrix (positive for likely substitutions, negative for unlikely ones).

Step 6 — Assess statistical significance (the E-value). See below — this is the part students most misunderstand.

The scoring & statistics (derived, not dumped)

Deriving the E-value

Why this form?

The bigger the search space $m\times n$ , the more chances for a random high score → $E \propto mn$ . (Search a bigger haystack, expect more lucky matches.)
Higher score $S$ is exponentially harder to reach by chance → the $e^{-\lambda S}$ factor. Random alignment scores follow an extreme-value (Gumbel) distribution, whose tail decays like $e^{-\lambda S}$ .
Putting them together gives $E = Kmn\,e^{-\lambda S}$ .

The BLAST family (pick the right tool)

Program	Query	Database	Use when…
blastn	DNA	DNA	comparing nucleotide sequences
blastp	protein	protein	comparing proteins
blastx	DNA (translated 6 frames)	protein	annotating an unknown DNA/EST
tblastn	protein	DNA (translated)	find gene in unannotated genome
tblastx	DNA (transl.)	DNA (transl.)	deep, sensitive DNA comparison
PSI-BLAST	protein → profile	protein	detect distant homologs iteratively

Worked examples

Common mistakes (Steel-manned)

Active-recall flashcards

What does BLAST stand for?

Basic Local Alignment Search Tool

What is homology (precise definition)?

Descent of two sequences from a common ancestor (a yes/no evolutionary statement)

Why is similarity used to infer homology?

Functionally important regions are conserved by selection; high similarity is unlikely by chance, so it implies shared ancestry

What is a "seed" in BLAST?

A short exact (or neighbourhood) word match used as an anchor to start extending an alignment

What core trade-off does BLAST make?

It sacrifices guaranteed optimal alignment (heuristic) for a huge gain in speed

Write the E-value formula and define each term.

E = K·m·n·e^(−λS); m = query length, n = database size, S = alignment score, K,λ = fitted constants

Does a higher or lower E-value mean a better hit?

Lower E-value = better (fewer expected chance hits)

Why does E increase with database size n?

Larger search space gives more opportunities for a random alignment to reach a given score

What does the substitution-matrix score s(a,b) represent?

A log-odds ratio: log of (observed pair frequency in homologs / frequency expected by chance)

Why use logarithms in scoring?

So per-position scores add along the alignment (log turns a product of probabilities into a sum)

Which BLAST program: unknown DNA vs protein database?

blastx (translates DNA in 6 frames, searches proteins)

How does PSI-BLAST detect distant homologs?

It builds a position-specific scoring matrix (PSSM) from initial hits and iteratively re-searches

What does low-complexity masking prevent?

False high-scoring hits from repetitive/simple regions like poly-A or poly-Q

Approx relation between E and p-value for small E?

p ≈ 1 − e^(−E) ≈ E

Recall Feynman: explain to a 12-year-old

You have a weird word and want to know its meaning, but there's no definition — only a giant library of known words. Instead of reading every book, you look for short chunks of your word that match chunks in the library ("seed" clues). When you find a chunk, you read outward from it to see how much of the whole word matches. If a library word matches almost perfectly, your weird word probably means the same thing (they're "cousins"). BLAST also tells you: "Could this match just be luck?" — if it says "you'd basically never get this by luck" (a super-tiny E-value), you can trust it.

Connections

Sequence Alignment (Global vs Local) — Needleman–Wunsch vs Smith–Waterman
Substitution Matrices (BLOSUM and PAM) — where $s(a,b)$ comes from
Molecular Evolution and Conserved Domains — why conservation predicts function
Multiple Sequence Alignment and Phylogenetics — next step after finding homologs
Gene and Genome Annotation — BLAST as an annotation workhorse
Extreme Value / Gumbel Distribution — statistical basis of the E-value
Dynamic Programming — the exact algorithms BLAST approximates

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho tumhe lab mein ek anjaan (unknown) DNA ya protein sequence mila, aur tumhe pata karna hai ki ye karta kya hai. Har cheez wet-lab mein test karna mahina lag jaayega. Iska shortcut hai BLAST — ek search engine jo billions of known sequences mein se tumhare sequence se milte-julte (similar) sequences dhoondh deta hai. Logic simple hai: agar tumhara sequence kisi already-studied protein se bahut milta hai, to dono ka common ancestor hai (yani homologous hain), aur mostly same kaam bhi karte hain — kyunki evolution important regions ko conserve karta hai.

BLAST fast kaise hai? Poora optimal alignment karna (Smith–Waterman) bahut slow hai. To BLAST seed-and-extend trick use karta hai: pehle sequence ko chhote-chhote words (k-mers) mein todta hai, database mein un words ke exact matches (seeds) dhoondta hai, aur sirf un seeds ke aas-paas alignment ko extend karta hai. Isse speed bahut badh jaati hai — thoda accuracy ka risk hai (heuristic hai), par practically ye kaam kar jaata hai.

Sabse important cheez samajhna: E-value. Formula hai $E = Kmne^{-\lambda S}$ . Iska matlab: "itna accha (ya usse behtar) match sirf luck se kitni baar aata?" Agar $E$ bada hai (jaise 10) to match sirf random noise hai; agar $E$ bahut chhota hai (jaise $10^{-40}$ ) to match real hai, chance se aa hi nahi sakta. Yaad rakho: E-value jitna chhota, utna accha (score ke ulta). Aur ek confusion mat karna — "45% homologous" galat hai; homology to yes/no hoti hai, tum sirf % identity/similarity bolte ho aur usse homology infer karte ho.

Test yourself — Bioinformatics & Computational Biology

Connections