Neural Sync Active

Learning Objectives

Registry Synced

Learning Objectives

323 words

2 min read

Reading compass

Now · 1. Needleman-Wunsch (Global Alignment)

Learning Objectives

Understand pairwise alignment with dynamic programming
Distinguish global (Needleman-Wunsch) and local (Smith-Waterman) alignment
Interpret alignment scores

1. Needleman-Wunsch (Global Alignment)

Aligns entire sequences end-to-end. Best for closely related sequences of similar length. Dynamic Programming: F(i,j) = max(F(i-1,j-1)+s(xi,yj), F(i-1,j)-gap, F(i,j-1)-gap) Fill scoring matrix, then traceback from bottom-right to top-left to get alignment.

2. Smith-Waterman (Local Alignment)

Finds best local alignment (subsequences). Better for divergent sequences, domains. Key difference: F(i,j) cannot be negative (reset to 0). Traceback from highest scoring cell.

3. Scoring Systems

Match/mismatch: from substitution matrix (BLOSUM62 for proteins, identity matrix for DNA). Gap penalties: linear = g_k or affine = d+e_(k-1) where d=open, e=extend.

4. Time Complexity

O(n*m) time and memory. For two sequences of length 1000, matrix has 1,000,000 cells. This is why BLAST (heuristic) is needed for database searching.

Q1: What is the difference between global and local alignment?

Global (Needleman-Wunsch): aligns entire sequences end-to-end. Good for closely related sequences of similar length. Local (Smith-Waterman): finds best matching subsequences. Good for divergent sequences, protein domains. Q2: Why use affine gap penalties?

Opening a gap is biologically rare (costly), but extending an existing gap is easier (cheaper). Affine: d+e*(k-1). Linear: g*k (less biologically accurate). Q3: How does BLOSUM62 matrix affect alignment?

Provides substitution scores based on observed frequencies in related proteins. Positive for common substitutions (conservative), negative for rare ones. More biologically meaningful than simple +1/-1. Q4: Time complexity of Needleman-Wunsch?

O(n*m). For n=m=1000: 1 million cells. For database searching with millions of sequences, this is too slow, requiring heuristic approaches like BLAST. Q5: What is the traceback step?

After filling the scoring matrix, traceback starts at the end cell (global) or highest-scoring cell (local). Follows arrows back: diagonal = match/mismatch, up/left = gap. Produces the optimal alignment. Join Discord PreviousMolecular Biology RefresherNextBLAST & Database Searching