Sequence Alignment & Phylogenetics
Course Overview
This course teaches the mathematical and computational foundations of sequence alignment and phylogenetics. Students move from understanding alignment algorithms at the code level to generating publication-quality phylogenetic trees from real data. This course is central to evolutionary biology, comparative genomics, and molecular epidemiology.
Learning Outcomes
1. Implement Needleman-Wunsch and Smith-Waterman alignment algorithms from first principles.
2. Perform and evaluate multiple sequence alignments using ClustalW and MAFFT.
3. Select appropriate substitution models for phylogenetic inference.
4. Construct and interpret maximum likelihood and Bayesian phylogenetic trees.
5. Annotate and publish phylogenetic trees with iTOL and FigTree.
Curriculum Content
Week 1: Pairwise Sequence Alignment Algorithms
• Global alignment (Needleman-Wunsch): fill the DP matrix, traceback, affine gap penalties — why gap extension penalty differs from gap opening.
• Local alignment (Smith-Waterman): similarities and differences; BLAST as a heuristic implementation.
• Scoring matrices: PAM vs. BLOSUM families; log-odds scores; when to use BLOSUM62 vs. BLOSUM45.
• Statistical significance: E-value vs. p-value; random sequence baseline; extreme value distribution.
Week 2: Multiple Sequence Alignment
• Progressive alignment (ClustalW): guide tree construction, profile-profile alignment, limitations.
• Iterative alignment (MAFFT, MUSCLE): FFTNS, FFT-NW, accuracy benchmarks on BAliBASE.
• Alignment columns: informative vs. invariant vs. parsimony-uninformative sites.
• Alignment QA: TrimAl for trimming poorly aligned regions; Gblocks; manual inspection in Jalview.
Weeks 3–4: Phylogenetics
• Substitution models: Jukes-Cantor, Kimura 2-parameter, GTR; model selection with jModelTest/ModelFinder.
• Tree construction methods: neighbour-joining (phenetic), maximum parsimony, maximum likelihood, Bayesian inference.
• Bootstrap support and posterior probability: interpreting support values; what counts as "significant" support.
• Tree rooting: outgroup selection, midpoint rooting, molecular clock.
• Biological interpretation: monophyly, paraphyly, polyphyly; convergent evolution; horizontal gene transfer signals.
Hands-On Practicals
🔬 Hands-On Lab: Needleman-Wunsch from Scratch in Python
Step 1: Implement the Needleman-Wunsch algorithm in Python using a match=+1, mismatch=-1, gap=-2 scoring scheme.
Step 2: Test your implementation on these sequences: GCATGCU and GATTACA.
Step 3: Modify to use affine gap penalties (gap open = -5, gap extend = -0.5) and compare the resulting alignment.
Step 4: Verify your results against BioPython pairwise2.align.globalms().
Step 5: Discuss: why does the choice of gap penalty change the alignment? Give a biological justification.
# Needleman-Wunsch in Python
import numpy as np
def nw_align(seq1, seq2, match=1, mismatch=-1, gap=-2):
m, n = len(seq1), len(seq2)
score = np.zeros((m+1, n+1))
# Initialise
for i in range(m+1): score[i][0] = i * gap
for j in range(n+1): score[0][j] = j * gap
# Fill
for i in range(1, m+1):
for j in range(1, n+1):
diag = score[i-1][j-1] + (match if seq1[i-1]==seq2[j-1] else mismatch)
up = score[i-1][j] + gap
left = score[i][j-1] + gap
score[i][j] = max(diag, up, left)
return score
seq1, seq2 = "GCATGCU", "GATTACA"
matrix = nw_align(seq1, seq2)
print(f"Alignment score: {matrix[-1][-1]}")
🔬 Hands-On Lab: IQ-TREE Maximum Likelihood Phylogenetics
Step 1: Download 20 cytochrome b sequences from NCBI (across vertebrates) in FASTA format.
Step 2: Align sequences with MAFFT (online or command line): mafft --auto sequences.fasta > aligned.fasta
Step 3: Trim with TrimAl: trimal -in aligned.fasta -out trimmed.fasta -automated1
Step 4: Run IQ-TREE: iqtree2 -s trimmed.fasta -m TEST -bb 1000 -alrt 1000 -nt AUTO
Step 5: Visualise and annotate the tree in iTOL (itol.embl.de) — colour branches by taxonomic class.
Step 6: Interpret: which groups are monophyletic? Are any relationships surprising?