Skip to content

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 read
  • Updated
On this page · 15 sections
  1. Prerequisites
  2. The Hook: The Oncogene That Was a Growth Factor
  3. Homology, Similarity and Identity
  4. Dot Plots: Alignment You Can See
  5. Scoring Matrices
  6. Pairwise Alignment by Dynamic Programming
  7. Database Search: FASTA and BLAST
  8. Multiple Sequence Alignment (MSA)
  9. Memory Tricks
  10. Don’t Confuse
  11. Common Mistakes
  12. Practice
  13. Quick Revision Table
  14. Key Takeaways
  15. What’s Next

Prerequisites

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

TermMeaningMeasured?
IdentityFraction of aligned positions with the same residueYes (%)
SimilarityFraction of aligned positions with the same or a conservative substitution (positive score in the matrix)Yes (%)
HomologyDescent from a common ancestorNo: 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

TermArises byExample
OrthologuesSpeciation: the same gene in two species, traced to their last common ancestorHuman β-globin and mouse β-globin
ParaloguesGene duplication within a lineageHuman α-globin and β-globin; myoglobin and the haemoglobin chains
In-paralogues / out-paraloguesDuplication after / before the speciation event being consideredLineage-specific gene family expansions are in-paralogues
XenologuesHorizontal gene transferAntibiotic-resistance genes moved between bacteria
AnaloguesConvergent evolution, no common ancestrySubtilisin 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.

PatternMeaning
Main diagonal lineThe sequences are similar along their length
Diagonal broken by a horizontal or vertical offsetAn insertion or deletion
Several parallel diagonalsInternal repeats
Short line perpendicular to the main diagonal, in a sequence compared with itselfA 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 onlyNo 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

FeaturePAM (Point Accepted Mutation; Dayhoff)BLOSUM (BLOcks SUbstitution Matrix; Henikoff and Henikoff, 1992)
Data sourceGlobal alignments of closely related proteinsUngapped blocks (BLOCKS database) of conserved regions of more distantly related proteins
How the series is madePAM1 = 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 meansEvolutionary distance: PAM250 = 250 accepted mutations per 100 residuesClustering identity threshold: BLOSUM62 from blocks clustered at 62%
For distant sequences useHigher PAM (PAM250)Lower BLOSUM (BLOSUM45)
For close sequences useLower 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:

  1. A fourth option, 0, in the max (negative scores reset to zero).
  2. First row and column are 0.
  3. 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)
AlignsFull lengthBest sub-region
Use whenSequences 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 floorNone0
Traceback fromBottom-right cellHighest-scoring cell
Semi-global (“glocal”) variantEnd 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)

  1. Hash the query into words of length ktup (typically 2 for proteins, 6 for DNA) and find identical word matches in each database sequence.
  2. Find the ten best diagonal regions with the most word hits; rescore them with a substitution matrix. The best single region gives init1.
  3. Join compatible regions allowing gaps; the joined score is initn.
  4. Run a banded Smith–Waterman around the best region to give the opt score.
  5. 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

ProgramQueryDatabaseComparison
blastnNucleotideNucleotideNucleotide vs nucleotide
blastpProteinProteinProtein vs protein
blastxNucleotide, translated in 6 framesProteinTranslated query vs protein
tblastnProteinNucleotide, translated in 6 framesProtein vs translated database
tblastxNucleotide, translatedNucleotide, translatedBoth 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'}$$
QuantityDepends on database size?Interpretation
Raw score SNoSum of matrix scores and gap penalties
Bit score S'NoNormalised; comparable between searches and matrices
E-valueYes (proportional to n)Number of hits this good expected by chance in this search
P-valueYes\(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).

StrategyProgramsIdeaWeakness
ProgressiveClustalW, 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 refinementMUSCLE, MAFFT (iterative modes)Progressive draft, then repeatedly split, realign and keep improvementsSlower; still heuristic
Consistency-basedT-CoffeeLibrary of pairwise global and local alignments; favours pairs that agree across many tripletsSlow for many sequences
Structure-aware(e.g. using known 3D structures)Align by superposed structures where availableNeeds 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

ThisvsThat
Homology: common ancestry, yes/novsSimilarity/identity: measured percentages
Orthologue: speciationvsParalogue: duplication
Paralogue: shared ancestryvsAnalogue: convergence, no shared ancestry
Needleman–Wunsch: global, bottom-right cellvsSmith–Waterman: local, zero floor, highest cell
PAM: extrapolated, close sequencesvsBLOSUM: measured, conserved blocks
blastx: translated queryvstblastn: translated database
Bit score: independent of database sizevsE-value: grows with database size
BLAST: words + extensionvsFASTA: k-tuples, diagonals, banded SW
Progressive MSA: fast, errors frozenvsIterative MSA: refines the draft
PSSM: scores per positionvsProfile 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

  1. Which DP algorithm gives the optimal local alignment?
  2. Which BLAST program compares a protein query with a nucleotide database translated in all six frames?
  3. Genes related by duplication within one genome are called what?
Answers
  1. Smith–Waterman.
  2. tblastn.
  3. 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
  1. Matrix (first row and column are multiples of −2):
–GATG
–0−2−4−6−8
G−21−1−3−5
C−4−10−2−4
A−6−30−1−3
T−8−5−21−1
G−10−7−4−12
  1. 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.

  1. 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
  1. \(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}\).
  2. \(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.
  3. E doubles to about 4.1 × 10⁻⁴; the bit score is unchanged (it does not depend on n).
  4. 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

ItemFact
HomologyCommon ancestry, not a percentage
Orthologue / paralogue / xenologue / analogueSpeciation / duplication / HGT / convergence
Log-odds scores = (1/λ) ln(q_ab / p_a p_b); positive = more than chance
PAMDayhoff; PAM1 = 1% change; extrapolated; PAM250 for distant
BLOSUMHenikoff 1992; BLOCKS; clustered at X%; BLOSUM62 default; BLOSUM45 distant
BLOSUM62 highlightsW–W 11, C–C 9
Affine gapW = G_o + k G_e; blastp default 11/1
Needleman–WunschGlobal; F(i,0) = ig; answer bottom-right
Smith–WatermanLocal; floor 0; highest cell; stop at 0
DP costTime and memory ∝ m × n
FASTAktup 2 (protein), 6 (DNA); init1, initn, opt
BLASTWords (w = 3 protein classic, 11 blastn, 28 megablast), threshold T, extension, HSP
BLAST programsblastn, blastp, blastx (query translated), tblastn (db translated), tblastx (both)
E-valueE = Kmn e^(−λS) = mn 2^(−S’); ∝ database size
Bit scoreS’ = (λS − ln K)/ln 2; database-independent
PSI-BLASTIterative PSSM; remote homologues; profile drift risk
MSAProgressive (ClustalW, guide tree), iterative (MUSCLE, MAFFT), consistency (T-Coffee)
Clustal symbols* identical, : strong, . weak
LogoIC = log₂N − H; DNA max 2 bits

Key Takeaways

What’s Next