Sequence Alignment: Scoring Matrices, BLAST, FASTA and Multiple Alignment
Homologues, orthologues and paralogues, PAM and BLOSUM, gap penalties, Needleman-Wunsch, Smith-Waterman, BLAST and FASTA statistics, MSA for CSIR NET.
- 20 min
On this page · 15 sections
- Prerequisites
- The Hook: The Oncogene That Was a Growth Factor
- Homology, Similarity and Identity
- Dot Plots: Alignment You Can See
- Scoring Matrices
- Pairwise Alignment by Dynamic Programming
- Database Search: FASTA and BLAST
- Multiple Sequence Alignment (MSA)
- Memory Tricks
- Don’t Confuse
- Common Mistakes
- Practice
- Quick Revision Table
- Key Takeaways
- What’s Next
Prerequisites
- Bioinformatic Resources and Databases — the databases that BLAST and FASTA search, and the FASTA format.
- Protein Structure, Conformation and Stability — why some amino-acid substitutions are tolerated and others are not.
- Genes, Mutations and Fine-Structure Analysis — transitions, transversions and indels are what alignments record.
The Hook: The Oncogene That Was a Growth Factor
How CSIR NET asks it. Part B: which matrix for which divergence, local vs global, which BLAST program for which query, what the E-value means, orthologue vs paralogue. Part C: fill a small dynamic-programming matrix, compute an E-value or bit score, interpret a BLAST table or a gene tree.
Homology, Similarity and Identity
| Term | Meaning | Measured? |
|---|---|---|
| Identity | Fraction of aligned positions with the same residue | Yes (%) |
| Similarity | Fraction of aligned positions with the same or a conservative substitution (positive score in the matrix) | Yes (%) |
| Homology | Descent from a common ancestor | No: it is an inference, either true or false |
“These proteins are 40% homologous” is wrong usage. Say they are 40% identical, and therefore probably homologous.
Kinds of homologues
| Term | Arises by | Example |
|---|---|---|
| Orthologues | Speciation: the same gene in two species, traced to their last common ancestor | Human β-globin and mouse β-globin |
| Paralogues | Gene duplication within a lineage | Human α-globin and β-globin; myoglobin and the haemoglobin chains |
| In-paralogues / out-paralogues | Duplication after / before the speciation event being considered | Lineage-specific gene family expansions are in-paralogues |
| Xenologues | Horizontal gene transfer | Antibiotic-resistance genes moved between bacteria |
| Analogues | Convergent evolution, no common ancestry | Subtilisin and chymotrypsin share the Ser–His–Asp triad but have unrelated folds |
The terms orthologue and paralogue were introduced by Walter Fitch (1970). Orthologues are the default choice for transferring function between species and for building species trees; paralogues may have diverged in function (neofunctionalisation) or split the ancestral roles (subfunctionalisation).
graph TD
A["Ancestral gene"] --> D{"Duplication"}
D --> G1["Copy alpha"]
D --> G2["Copy beta"]
G1 --> S1{"Speciation"}
G2 --> S2{"Speciation"}
S1 --> HA["Human alpha"]
S1 --> MA["Mouse alpha"]
S2 --> HB["Human beta"]
S2 --> MB["Mouse beta"]In this tree, human α and mouse α are orthologues (they split at speciation); human α and human β are paralogues; human α and mouse β are also paralogues, because the node that joins them is the duplication.
Dot Plots: Alignment You Can See
Write one sequence along the x-axis and the other along the y-axis, and put a dot wherever residues (or, with a window and a stringency threshold, short stretches) match.
| Pattern | Meaning |
|---|---|
| Main diagonal line | The sequences are similar along their length |
| Diagonal broken by a horizontal or vertical offset | An insertion or deletion |
| Several parallel diagonals | Internal repeats |
| Short line perpendicular to the main diagonal, in a sequence compared with itself | A palindrome (a stretch that reads the same backwards); for DNA, an inverted repeat shows up this way when reverse-complement matches are also plotted |
| Scattered dots only | No significant similarity (noise; increase the window to suppress it) |
Scoring Matrices
An alignment score adds up a score for every aligned pair and a penalty for every gap. Substitution scores are log-odds values:
$$s(a,b) = \frac{1}{\lambda}\ln\frac{q_{ab}}{p_a\,p_b}$$where \(q_{ab}\) is how often residues a and b are observed aligned in trusted alignments of related proteins and \(p_a p_b\) is how often they would pair by chance. Positive score: the substitution occurs more often than chance (conservative, for example Ile ↔ Val). Negative: less often than chance. Scores are scaled and rounded to integers.
PAM vs BLOSUM
| Feature | PAM (Point Accepted Mutation; Dayhoff) | BLOSUM (BLOcks SUbstitution Matrix; Henikoff and Henikoff, 1992) |
|---|---|---|
| Data source | Global alignments of closely related proteins | Ungapped blocks (BLOCKS database) of conserved regions of more distantly related proteins |
| How the series is made | PAM1 = 1 accepted mutation per 100 residues; higher PAMs by extrapolation (multiplying the PAM1 matrix by itself) | Each matrix measured directly: sequences more identical than X% are clustered, then counted |
| Number means | Evolutionary distance: PAM250 = 250 accepted mutations per 100 residues | Clustering identity threshold: BLOSUM62 from blocks clustered at 62% |
| For distant sequences use | Higher PAM (PAM250) | Lower BLOSUM (BLOSUM45) |
| For close sequences use | Lower PAM (PAM30, PAM70) | Higher BLOSUM (BLOSUM80) |
| Default | — | BLOSUM62, the default for protein BLAST |
Key features of BLOSUM62: identities score highest for rare, structurally special residues (Trp–Trp = 11, Cys–Cys = 9) and lowest for common, easily replaced ones; Ile/Leu/Val/Met swaps score positive; Trp ↔ Gly and most substitutions of Cys score negative. PAM250 still aligns sequences that are only about 20% identical, because many positions have changed more than once.
DNA scoring is simpler: a match/mismatch pair (BLASTN commonly uses +1/−2 or +2/−3 type schemes), or a matrix that penalises transversions more than transitions.
Gap penalties
A gap of length \(k\) is penalised with an affine function:
$$W(k) = G_o + k\,G_e \qquad\text{(BLAST convention: existence cost + } k \times \text{extension cost)}$$Opening is expensive and extending cheap, because one indel event often removes or inserts several residues at once. Protein BLAST’s usual default with BLOSUM62 is existence 11, extension 1, so a 4-residue gap costs 11 + 4 = 15. (Some programs write \(G_o + (k-1)G_e\); always check the convention a question states.) A linear penalty (\(k \times g\)) is used in hand-worked examples.
Pairwise Alignment by Dynamic Programming
Dynamic programming (DP) guarantees the optimal alignment for a given scoring scheme by building it from optimal alignments of prefixes.
Global: Needleman–Wunsch (1970)
Aligns the whole length of both sequences. Fill a matrix F with
$$F(i,j) = \max\begin{cases} F(i-1,j-1) + s(x_i,y_j) & \text{(match/mismatch, diagonal)}\\ F(i-1,j) + g & \text{(gap in } y\text{, from above)}\\ F(i,j-1) + g & \text{(gap in } x\text{, from left)}\end{cases}$$with \(F(0,0) = 0\), first row and column \(F(i,0) = i\,g\) and \(F(0,j) = j\,g\). The optimal score is in the bottom-right cell; traceback from there to (0,0) recovers the alignment.
Local: Smith–Waterman (1981)
Finds the best-matching sub-region. Three changes from Needleman–Wunsch:
- A fourth option, 0, in the max (negative scores reset to zero).
- First row and column are 0.
- Traceback starts at the highest cell anywhere in the matrix and stops at the first 0.
For local alignment to work the scoring scheme must give negative expected scores for random pairs; otherwise the “local” alignment just extends over everything.
Cost. Both algorithms take time and memory proportional to \(m \times n\) (product of the lengths). That is fine for two genes but far too slow for comparing a query against hundreds of billions of database residues many times a day, which is why heuristic methods exist.
| Global (Needleman–Wunsch) | Local (Smith–Waterman) | |
|---|---|---|
| Aligns | Full length | Best sub-region |
| Use when | Sequences of similar length, similar along their length (orthologues, close homologues) | Shared domain or motif in otherwise different proteins; a gene inside a genomic region |
| Matrix floor | None | 0 |
| Traceback from | Bottom-right cell | Highest-scoring cell |
| Semi-global (“glocal”) variant | End gaps not penalised: fits a short read inside a long reference |
Database Search: FASTA and BLAST
Both are heuristics: they skip most of the DP matrix by looking only around short exact (or high-scoring) word matches. They are much faster than full Smith–Waterman and can occasionally miss the optimal alignment.
FASTA (Lipman and Pearson)
- Hash the query into words of length ktup (typically 2 for proteins, 6 for DNA) and find identical word matches in each database sequence.
- Find the ten best diagonal regions with the most word hits; rescore them with a substitution matrix. The best single region gives init1.
- Join compatible regions allowing gaps; the joined score is initn.
- Run a banded Smith–Waterman around the best region to give the opt score.
- Estimate significance (E-values) from the distribution of scores of unrelated database sequences.
Smaller ktup = more sensitive, slower. The FASTA format (> header line) comes from this program.
BLAST (Basic Local Alignment Search Tool; Altschul et al., 1990)
graph LR
Q["Query"] --> W["1. Break into words
protein w = 3 (classic),
blastn w = 11"]
W --> N["2. Neighbourhood words
scoring at least T
with the matrix"]
N --> S["3. Scan database
for exact word hits
(seeds)"]
S --> E["4. Extend seeds
ungapped, then gapped,
stop on X-drop"]
E --> H["5. HSPs scored;
E-values computed;
alignments reported"]- Neighbourhood words (proteins): not only the exact word but all words scoring at least a threshold T against it with BLOSUM62 are used as seeds. Lower T = more seeds, more sensitive, slower.
- Two-hit method (gapped BLAST, 1997): extension starts only when two seeds fall on the same diagonal within a set distance, saving time.
- HSP (high-scoring segment pair): a locally optimal aligned segment.
- Low-complexity filtering masks regions such as poly-Q or AT-rich repeats (SEG for proteins, DUST for DNA) that would otherwise give many spurious hits.
- MEGABLAST uses very long words (28 by default) for near-identical DNA, for example mapping a sequence to its own genome.
BLAST programs
| Program | Query | Database | Comparison |
|---|---|---|---|
| blastn | Nucleotide | Nucleotide | Nucleotide vs nucleotide |
| blastp | Protein | Protein | Protein vs protein |
| blastx | Nucleotide, translated in 6 frames | Protein | Translated query vs protein |
| tblastn | Protein | Nucleotide, translated in 6 frames | Protein vs translated database |
| tblastx | Nucleotide, translated | Nucleotide, translated | Both translated (slowest) |
Variants: PSI-BLAST (position-specific iterated) builds a PSSM from the hits of each round and searches again, finding remote homologues; the danger is profile drift if an unrelated sequence is included and pulls in its own family. PHI-BLAST requires a given pattern in the hits. DELTA-BLAST starts from a conserved-domain profile.
How significant is a hit? Karlin–Altschul statistics
Scores of optimal local alignments between random sequences follow an extreme value (Gumbel) distribution, not a normal one. The expected number of chance hits scoring at least S is
$$\boxed{E = K\,m\,n\,e^{-\lambda S}}$$with m = query length, n = total database length (residues), and K and λ constants that depend on the scoring system. The bit score removes K and λ:
$$S' = \frac{\lambda S - \ln K}{\ln 2}, \qquad E = m\,n\,2^{-S'}$$| Quantity | Depends on database size? | Interpretation |
|---|---|---|
| Raw score S | No | Sum of matrix scores and gap penalties |
| Bit score S' | No | Normalised; comparable between searches and matrices |
| E-value | Yes (proportional to n) | Number of hits this good expected by chance in this search |
| P-value | Yes | \(P = 1 - e^{-E}\); for small E, P ≈ E |
Consequences that exam questions test:
- Lower E = more significant. E = 10⁻⁵⁰ is a near-certain homologue; E = 5 means five such hits are expected by chance.
- E doubles when the database doubles (same score). The same alignment becomes “less significant” as databases grow.
- E falls exponentially with score: each extra bit halves E.
- Short queries cannot reach very low E-values even with perfect identity, because their maximum possible score is small.
- There is no universal cut-off; a threshold such as 10⁻³ or smaller is a common working convention.
Multiple Sequence Alignment (MSA)
An MSA aligns three or more sequences so that each column holds residues assumed to be homologous. It is the input for phylogenetics, profiles, HMMs, conservation analysis, primer design and structure prediction.
Exact DP for N sequences of length L needs a matrix of size about \(L^N\): impossible beyond a few sequences. So all practical methods are heuristics, scored for example by the sum-of-pairs score (add the pairwise scores of every pair in each column).
| Strategy | Programs | Idea | Weakness |
|---|---|---|---|
| Progressive | ClustalW, Clustal Omega | (1) all pairwise alignments → distance matrix; (2) guide tree (for example neighbour-joining); (3) align sequences and profiles in the order of the tree | “Once a gap, always a gap”: early errors are frozen in |
| Iterative refinement | MUSCLE, MAFFT (iterative modes) | Progressive draft, then repeatedly split, realign and keep improvements | Slower; still heuristic |
| Consistency-based | T-Coffee | Library of pairwise global and local alignments; favours pairs that agree across many triplets | Slow for many sequences |
| Structure-aware | (e.g. using known 3D structures) | Align by superposed structures where available | Needs structures |
Clustal output marks each column: * fully conserved, : conserved strongly similar groups, . weakly similar groups.
From an MSA to a model
- Consensus sequence: the most common residue in each column.
- PSSM / profile: a log-odds score for every residue at every position.
- Profile HMM: match, insert and delete states for each column, with emission and transition probabilities (HMMER; the models in Pfam).
- Sequence logo: stack height at each position = information content in bits, \(IC = \log_2 N - H\), where \(H = -\sum p_i \log_2 p_i\) and N = 4 (DNA) or 20 (protein). A fully conserved DNA position carries 2 bits; a column with A 0.5, C 0.25, G 0.25 has H = 1.5 bits and IC = 0.5 bits.
Comparative genomics: alignment at genome scale
Whole genomes are compared with fast aligners that find anchors (long exact or near-exact matches) and fill in between them. The results show synteny (conserved gene order), rearrangements and conserved non-coding elements; they are covered on the phylogenetics and comparative genomics page.
Memory Tricks
Don’t Confuse
| This | vs | That |
|---|---|---|
| Homology: common ancestry, yes/no | vs | Similarity/identity: measured percentages |
| Orthologue: speciation | vs | Paralogue: duplication |
| Paralogue: shared ancestry | vs | Analogue: convergence, no shared ancestry |
| Needleman–Wunsch: global, bottom-right cell | vs | Smith–Waterman: local, zero floor, highest cell |
| PAM: extrapolated, close sequences | vs | BLOSUM: measured, conserved blocks |
| blastx: translated query | vs | tblastn: translated database |
| Bit score: independent of database size | vs | E-value: grows with database size |
| BLAST: words + extension | vs | FASTA: k-tuples, diagonals, banded SW |
| Progressive MSA: fast, errors frozen | vs | Iterative MSA: refines the draft |
| PSSM: scores per position | vs | Profile HMM: adds position-specific gap probabilities |
Common Mistakes
Practice
All questions below are original practice questions written in CSIR NET style. They are not previous-year questions; this unit is new in the revised syllabus.
Level 1: Foundation
- Which DP algorithm gives the optimal local alignment?
- Which BLAST program compares a protein query with a nucleotide database translated in all six frames?
- Genes related by duplication within one genome are called what?
Answers
- Smith–Waterman.
- tblastn.
- Paralogues.
Level 2: Part B Style
Q1 (practice). A pairwise protein alignment is 120 columns long. 84 columns are identical pairs and 12 columns contain a gap. Percent identity calculated over the whole alignment, and over the ungapped columns only, is:
- (a) 70% and 77.8%
- (b) 77.8% and 70%
- (c) 70% and 70%
- (d) 84% and 77.8%
Answer and explanation
(a). Over the alignment: 84/120 = 70%. Over ungapped columns: 84/(120 − 12) = 84/108 = 77.8%. Programs differ in which denominator they use, so always read the definition.
Q2 (practice). You want to find distant homologues of a protein that share about 25% identity. Which matrix choice is most appropriate?
- (a) PAM30
- (b) BLOSUM80
- (c) BLOSUM45 or PAM250
- (d) An identity matrix (match +1, mismatch 0)
Answer and explanation
(c). Distant sequences need a high PAM or a low BLOSUM. PAM30 and BLOSUM80 suit close sequences; an identity matrix ignores conservative substitutions and loses sensitivity.
Q3 (practice). Using the BLAST convention W(k) = existence + k × extension, with existence 11 and extension 1, the penalty for one gap of 4 residues and for four separate 1-residue gaps is:
- (a) 15 and 48
- (b) 15 and 15
- (c) 44 and 48
- (d) 14 and 44
Answer and explanation
(a). One 4-residue gap: 11 + 4 × 1 = 15. Four 1-residue gaps: 4 × (11 + 1) = 48. Affine penalties prefer one long gap to many short ones, matching how indels arise.
Q4 (practice). A blastp hit has a bit score of 50 when a 300-residue query is searched against a database of 10⁹ residues. The E-value is closest to:
- (a) 2.7 × 10⁻¹⁰
- (b) 2.7 × 10⁻⁴
- (c) 0.27
- (d) 50
Answer and explanation
(b). \(E = m n 2^{-S'} = 300 \times 10^9 \times 2^{-50} = 3\times10^{11} / 1.126\times10^{15} \approx 2.7\times10^{-4}\).
Level 3: Part C Style
Q1 (practice). Align x = GCATG (rows) and y = GATG (columns) globally with match +1, mismatch −1 and linear gap −2.
(i) Fill the DP matrix. (ii) Give the optimal score and the alignment. (iii) If the same sequences were aligned locally (Smith–Waterman, same scores), would the best score be higher or lower, and what would the alignment be?
Answer and worked solution
- Matrix (first row and column are multiples of −2):
| – | G | A | T | G | |
|---|---|---|---|---|---|
| – | 0 | −2 | −4 | −6 | −8 |
| G | −2 | 1 | −1 | −3 | −5 |
| C | −4 | −1 | 0 | −2 | −4 |
| A | −6 | −3 | 0 | −1 | −3 |
| T | −8 | −5 | −2 | 1 | −1 |
| G | −10 | −7 | −4 | −1 | 2 |
- Global score = 2. Traceback: G–G, T–T, A–A diagonals, then C against a gap, then G–G:
G C A T G
G - A T G
4 matches (+4) and one gap (−2) = 2.
- Higher. Locally, negative cells reset to 0 and the leading G and C need not be aligned at all. The best cell (value 3, at row G5, column G4) traces back through T–T and A–A to a zero: the local alignment is ATG / ATG, score +3 (3 > 2). Adding the first G would cost a gap (−2) for one match (+1), so it is left out.
Q2 (practice). A protein query of 250 residues is searched against a database of 5 × 10⁸ residues. For the scoring system, λ = 0.32 and K = 0.13. The best hit has a raw score of 100.
(i) Calculate the E-value. (ii) Calculate the bit score. (iii) What happens to the E-value and the bit score if the database doubles in size? (iv) By how much must the raw score rise to make E ten times smaller?
Answer and worked solution
- \(E = K m n e^{-\lambda S} = 0.13 \times 250 \times 5\times10^8 \times e^{-32} \approx 1.625\times10^{10} \times 1.27\times10^{-14} \approx 2.1\times10^{-4}\).
- \(S' = (\lambda S - \ln K)/\ln 2 = (32 - \ln 0.13)/0.693 = (32 + 2.04)/0.693 \approx 49.1\) bits. Check: \(m n 2^{-49.1} = 1.25\times10^{11}\times 1.65\times10^{-15} \approx 2.1\times10^{-4}\). Consistent.
- E doubles to about 4.1 × 10⁻⁴; the bit score is unchanged (it does not depend on n).
- Need \(e^{-\lambda \Delta S} = 0.1\), so \(\Delta S = \ln 10/\lambda = 2.303/0.32 \approx 7.2\). About 7 more raw score units (equivalently \(\log_2 10 \approx 3.3\) more bits).
Q3 (practice). A gene tree is built for a gene family from human, mouse and chicken (species tree: human and mouse are closer to each other than either is to chicken). Human genes H1 and H2 group together as a pair; this pair is sister to a single mouse gene, M1; a single chicken gene, C1, is the outgroup to all three. In Newick form: (((H1,H2),M1),C1);. Consider the statements:
(A) H1 and H2 are in-paralogues produced by a duplication in the human lineage after the human–mouse split. (B) H1 and M1 are orthologues; so are H2 and M1 (a one-to-many orthology). (C) H1 and H2 must have identical functions because they are paralogues. (D) If H1 were later lost, H2 would still be an orthologue of M1.
- (a) A, B and D only
- (b) A and C only
- (c) B and C only
- (d) A, B, C and D
Answer and worked solution
(a) A, B and D.
- (A) Correct: the duplication node joins only human genes, so it happened in the human lineage after it split from mouse (and chicken). Such lineage-specific duplicates are in-paralogues relative to that speciation.
- (B) Correct: the node joining the human pair to the mouse gene is a speciation node; both human copies are orthologous to M1 (one-to-many, or co-orthologues).
- (C) Wrong: paralogues often diverge (neofunctionalisation, subfunctionalisation). Nothing requires identical function.
- (D) Correct: orthology is defined by the speciation node, which is unchanged by losing one copy.
Quick Revision Table
| Item | Fact |
|---|---|
| Homology | Common ancestry, not a percentage |
| Orthologue / paralogue / xenologue / analogue | Speciation / duplication / HGT / convergence |
| Log-odds score | s = (1/λ) ln(q_ab / p_a p_b); positive = more than chance |
| PAM | Dayhoff; PAM1 = 1% change; extrapolated; PAM250 for distant |
| BLOSUM | Henikoff 1992; BLOCKS; clustered at X%; BLOSUM62 default; BLOSUM45 distant |
| BLOSUM62 highlights | W–W 11, C–C 9 |
| Affine gap | W = G_o + k G_e; blastp default 11/1 |
| Needleman–Wunsch | Global; F(i,0) = ig; answer bottom-right |
| Smith–Waterman | Local; floor 0; highest cell; stop at 0 |
| DP cost | Time and memory ∝ m × n |
| FASTA | ktup 2 (protein), 6 (DNA); init1, initn, opt |
| BLAST | Words (w = 3 protein classic, 11 blastn, 28 megablast), threshold T, extension, HSP |
| BLAST programs | blastn, blastp, blastx (query translated), tblastn (db translated), tblastx (both) |
| E-value | E = Kmn e^(−λS) = mn 2^(−S’); ∝ database size |
| Bit score | S’ = (λS − ln K)/ln 2; database-independent |
| PSI-BLAST | Iterative PSSM; remote homologues; profile drift risk |
| MSA | Progressive (ClustalW, guide tree), iterative (MUSCLE, MAFFT), consistency (T-Coffee) |
| Clustal symbols | * identical, : strong, . weak |
| Logo | IC = log₂N − H; DNA max 2 bits |
Key Takeaways
What’s Next
- Phylogenetics, Comparative Genomics, Gene Annotation and Variation — turning alignments into trees and genomes into annotated genes.
- Bioinformatic Resources and Databases — Pfam and PROSITE, the family models built from alignments.
- Molecular Modelling and Protein Structure Prediction — alignment to a template is the first step of homology modelling.
- Chapter overview and Quick Revision.