Dynamic programing
Global Alignment- Needleman Wunch
Sequence Alignment Algorithms
• The algorithm that drives global alignment is the Needleman-Wunsch
algorithm, and the algorithm that drives local alignment is the Smith-
Waterman algorithm.
• Both these algorithms are examples of dynamic programming.
Dynamic programming is a method for solving complex problems by
breaking them down into simpler subproblems.
• In the case of sequence alignment, dynamic programming involves
setting up a two-dimensional matrix in which one sequence is listed
vertically and the other sequence is listed horizontally; then
calculating the scores, one row at a time.
Needleman-Wunsch algorithm for global
alignment
Step 1 Initialization
Step 1 Initialization
Step 1 Initialization
-2 -2 -2 -2 -2
-2
-2
-2
-2
Step 2 Matrix Filling
Step 2 Matrix Filling
Step 2 Matrix Filling
Step 3 Trace back
Important steps for writing the alignment
• To write the alignment we have to consider the arrows not the values
• we have to write the aligned sequences from left to right
4
T& T is a match so C&C is a match so
the arrow goes the arrow goes
diagonally diagonally
G&G is a match so
the arrow goes
Diagonally again
Now A&T is a
mismatch so
the arrow goes
horizontally
towards the highest
Valued neighbor
Now A&A is a
mismatch again so
the arrow goes
diagonally
Final sequence alignment
