Explain sequence alignment (pairwise, multiple)

1. What exactly is an alignment?

Three column types:

Match — same letter (e.g. A / A)
Mismatch — different letters, i.e. a substitution (e.g. A / G)
Gap — a letter aligned to -, i.e. an insertion or deletion (indel)

2. Scoring: turning biology into numbers

3. Deriving Needleman–Wunsch from scratch

We want the optimal global alignment of $X = x_1\dots x_m$ and $Y = y_1\dots y_n$ .

Key insight (optimal substructure): look at the last column of any alignment. It must be exactly one of three cases:

$x_m$ aligned with $y_n$ (match/mismatch)
$x_m$ aligned with a gap
$y_n$ aligned with a gap

Whatever comes before that last column is itself an optimal alignment of the shorter prefixes. This is the property that makes dynamic programming work.

Let $F(i,j)$ = score of the best alignment of prefixes $x_1\dots x_i$ and $y_1\dots y_j$ .

HOW the traceback works: at each cell remember which of the three cases won; walk backwards along those arrows. A diagonal arrow → a match/mismatch column; up/left → a gap column.

Figure — Explain sequence alignment (pairwise, multiple)

4. Worked example — pairwise (Needleman–Wunsch)

Align GATTACA region simplified. Use $X =$ GCAT, $Y =$ GTAT. Scoring: match $+1$ , mismatch $-1$ , gap $g=1$ (so subtract 1).

Build $F$ (rows = X letters G,C,A,T; cols = Y letters G,T,A,T):

	–	G	T	A	T
–	0	-1	-2	-3	-4
G	-1	1	0	-1	-2
C	-2	0	0	-1	-2
A	-3	-1	-1	1	0
T	-4	-2	0	0	2

Why $F(1,1)=1$ ? G vs G = match, so $F(0,0)+1 = 1$ ; beats gap options $(-2)$ .
Why $F(4,4)=2$ ? T vs T match: $F(3,3)+1 = 1+1 = 2$ . Best.

Traceback from $F(4,4)=2$ :

G C A T
G - A T   →  G C A T
             G _ A T   (final)

One optimal alignment (score 2):

G C A T
G T A T

Why this step (T-A-T end)? The diagonal chain of matches G…A…T dominates; the C/T column is the one mismatch we accept because forcing a gap costs more.

5. Multiple Sequence Alignment (MSA)

6. Common mistakes (steel-manned)

7. Feynman + Mnemonic

Recall Explain to a 12-year-old (click to reveal)

Imagine two friends copied the same long sentence by hand, but each made typos and sometimes skipped or added words. To see how similar their copies are, you slide the sentences side by side and, where one person skipped a word, you leave a blank box (-). You slide until the most words line up. Counting the lined-up words = the score. Doing this for just two people is pairwise; lining up a whole classroom's copies at once is multiple — and it's so hard we first pair up the most similar friends, then add the rest one by one.

8. Active-recall flashcards

What biological event does a gap column represent?

An insertion or deletion (indel) in one sequence relative to the other.

Which algorithm gives optimal GLOBAL pairwise alignment?

Needleman–Wunsch (dynamic programming, end-to-end).

Which algorithm gives optimal LOCAL alignment and what's its key extra rule?

Smith–Waterman; it adds a max with 0 so scores can't go negative, resetting bad regions.

State the Needleman–Wunsch recurrence.

F(i,j)=max{ F(i-1,j-1)+s(x_i,y_j), F(i-1,j)-g, F(i,j-1)-g }.

Why use affine gap penalties instead of linear?

One indel is a single event; affine (open o, extend e, o>e) prefers one long gap over many short ones, matching biology.

Why can't we solve MSA optimally by extending DP?

Cost is O(L^k) for k sequences — exponential, computationally infeasible.

List the 3 steps of progressive alignment.

1) all pairwise distances, 2) build guide tree, 3) align progressively profile-to-profile from most similar.

What is the "once a gap, always a gap" problem?

In progressive MSA, gaps placed early are frozen and errors propagate; fixed by iterative refinement.

What is the Sum-of-Pairs score?

Sum over all columns of the pairwise substitution scores of every pair of sequences.

Global vs local — what's the true deciding factor?

How much of the sequences is expected homologous (whole vs sub-region), not their length.

9. Connections

Dynamic Programming — the algorithmic backbone (optimal substructure).
BLOSUM and PAM matrices — where substitution scores $s(a,b)$ come from.
BLAST — heuristic local alignment for database search (E-values).
Phylogenetic Trees — MSA is the input to build them; guide trees seed MSA.
Hidden Markov Models — profile HMMs generalise MSA scoring.
Homology and Orthology — the biological meaning alignment tries to infer.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho do DNA sequences ek hi ancestor se aayi hain, lekin evolution ne kuch letters change kar diye (mutation), kuch add/delete kar diye (indel). Sequence alignment ka matlab hai in dono ko ek doosre ke neeche rakh kar, beech mein zaroorat padne par dash (-) daal kar, aise slide karna ki maximum letters match ho jaayein. Isse humein pata chalta hai ki do sequences kitni related hain aur kaunse regions conserved (important) hain.

Do sequences ka alignment karne ke liye Needleman–Wunsch algorithm use hota hai — ye dynamic programming hai, matlab hum ek table (matrix) banate hain aur har cell mein teen choices ka maximum lete hain: diagonal (match ya mismatch), upar (gap), ya left (gap). Table bhar kar bottom-right corner tak pahunchte hain, wahi optimal score hai; phir traceback kar ke actual alignment nikaalte hain. Agar poori sequence match karani ho to ye global; agar sirf ek chhota best matching region chahiye to Smith–Waterman (local) — jismein ek extra rule hai: score kabhi 0 se neeche nahi jaata.

Jab 3 se zyada sequences ek saath align karni ho (Multiple Sequence Alignment), tab optimal DP possible nahi kyunki cost exponential ho jaati hai. Isliye progressive alignment (Clustal, MUSCLE, MAFFT) use hota hai: pehle sab pairs ki distance nikaalo, ek guide tree banao, aur sabse similar sequences pehle align karo, phir baaki ek-ek kar ke add karo. Yaad rakho — "once a gap, always a gap" — jaldi lagaaya gaya gap frozen ho jaata hai, isliye iterative refinement zaroori hota hai. Gap penalty mein affine (open bada, extend chhota) biology ko sabse achha model karta hai, kyunki ek lambi deletion ek hi event hai, kai chhoti nahi.

Test yourself — Bioinformatics & Computational Biology

Connections