Sequence Alignment
By: Shokoofeh Ghiam
Fall 2025
Shahid Beheshti University
Outline
• What is sequence alignment?
• Why it is important?
• Types of sequence alignments
• Exact Results
• Dynamic Programming
• Approximation Algorithm
• Center Star Method
• Heuristics
• Progressive Alignment: ClustalW
Why Alignment is important?
Global vs. Local alignment
Global vs. Local alignment
Global vs. Local alignment Example
Sequence Alignment Example
DNA Sequence 1
tcctctgcctctgccatcat- - - caaccccaaaagt
tcctgtgcatctgcaatcatgggcaaccccaaaagt
DNA Sequence 2
The sequences are padded with gaps (dashes) so that wherever possible, columns contain identical
characters from the sequences involved
Causes of Dissimilarity
• mutation: a nucleotide at a certain location is replaced by another
nucleotide
(e.g.: ATA → AGA)
• insertion: at a certain location one new nucleotide is inserted in
between two existing nucleotides
(e.g.: AA → AGA)
• deletion: at a certain location one existing nucleotide is deleted
(e.g.: ACTG → AC-G)
• indel: an insertion or a deletion
Multiple Sequence Alignment (MSA)
• Given k sequences 𝑆 = 𝑆1 𝑆2 . . . 𝑆𝑘
• A multiple alignment of 𝑆 is a set of k equal-length
sequences 𝑆1′ 𝑆2′ . . . 𝑆𝑘′ .
where 𝑆𝑖′ is obtained by inserting gaps into 𝑆𝑖 .
• Multiple sequence alignment problem aims to find a multiple
alignment which optimize certain score.
Example of Multiple Sequence Alignment (MSA)
S1 = ACG--GAGA
S2 = -CGTTGACA
S3 = AC-T-GA-A
S4 = CCGTTCAC-
The Importance of Alignment
Aligning these three sequences from humans, chimpanzees, and macaques allows us to determine
which positions in the sequence should be compared with one another.
In the unaligned sequences, 15 spots are identical; in the aligned sequences, 22 spots are identical.
Sum of Pair (SP) Distance
• Equivalently, we have SP-dist.
• Consider the multiple alignment S′ of S.
• SP-dist(a₁, …, aₖ) = Σ₁≤i<j≤k δ(aᵢ, aⱼ)
• where aᵢ can be any character or a space.
• The SP-dist of S′ is
• Σₓ SP-dist(S′₁[x], …, S′ₖ[x]).
Example of Multiple Sequence Alignment (MSA)
S1 = ACG--GAGA
S2 = --CGTTGACA
S3 = AC-T-GA-A
S4 = CCGTTCAC-
• Assume score of
• match and mismatch/insert/delete are 2 and -2, respectively.
• For position 1,
• SP-score(A,-A,C) = 2δ(A,-) + 2δ(A,C) + 2δ(A,A) + 2δ(C,-) = -8
• SP-score = -8 + 12 + 0 + 0 - 6 + 0 + 12 - 10 + 0 = 0
Exact Results :Dynamic Programming
Representing an Alignment as a path
Representing an Alignment as a path
weight[0][0] = 0
n = size(s1)
m = size(s2)
for i -> 0 to n:
for j -> 0 to m:
a = weight[i - 1][j - 1] + score(s1[i], s2[j]) // socre in the matrix
b = weight[i - 1][j] + penalty // penalty for skipping a character
c = weight[i][j - 1] + penalty
weight[i][j] = max(a, b, c)
return weight[n][m]
Smith-Waterman Algorithm
Smith-Waterman Algorithm
Smith-Waterman Algorithm
Smith-Waterman Algorithm
Smith-Waterman Algorithm
Smith-Waterman Algorithm
Smith-Waterman Algorithm for 3 sequences
Smith-Waterman Algorithm for 3 sequences
Score Calculation
Dynamic Programming Running Time
Approximation Algorithm: Center Star Method
Center Star Method Example
Converting Pairwise Alignment to MSA
Running Time of STAR Algorithm
Heuristics: Progressive Alignment: ClustalW
Steps of Progressive Multiple Sequence Alignment
• Compute pairwise distance scores for all pairs of sequences.
• Generate the guide tree to ensure that similar sequences are placed
closer together in the tree.
• Align the sequences progressively — one by one according to the
guide tree.
Steps of ClustalW
ClustalW Example
ClustalW Output