Scribd
Upload
13 views32 pages

Dynamic Programming Approach

The document discusses the Dynamic Programming Approach in bioinformatics for multiple sequence alignment (MSA), detailing its introduction by Richard Bellman and its application to align sequences for maximum similarity. It outlines the rules and steps for alignment, including matrix filling and scoring based on match, mismatch, and gap penalties. Examples are provided to illustrate the alignment process and scoring methodology.

Uploaded by

wardajamalmalik
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
13 views32 pages

Dynamic Programming Approach

The document discusses the Dynamic Programming Approach in bioinformatics for multiple sequence alignment (MSA), detailing its introduction by Richard Bellman and its application to align sequences for maximum similarity. It outlines the rules and steps for alignment, including matrix filling and scoring based on match, mismatch, and gap penalties. Examples are provided to illustrate the alignment process and scoring methodology.

Uploaded by

wardajamalmalik
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 32

(BS)-Course

BIOINFORMATICS

Dr. Faryal Mehwish Awan


Department of Medical Lab Technology (MLT)
The University of Haripur
Types of MSA

 Dynamic Programming Approach

 Progressive Method

 Iterative Method
Dynamic Programming Approach

 It was introduced by Richard Bellman in 1940

 Maximize a score of similarity to give maximum

match

 Maximum match= largest number of nucleotides

that can be match with others that want to quantify

sequence similarity between two sequences


Dynamic Programming Approach

 In fact, dynamic programming is applicable to align any

number of sequences

 Computes an optimal alignment for a given score

function

 Because of its high running time, it is not typically used

in practice
Rules

● 1st column and 1st row must be blank.


●1+M×1+N
● After 0 add the Progressive gap penalties.
● Fill the other boxes as: take the three values for
each box & Select the greater value.
1.Value from left + gap penalty
2.Value from top +gap penalty
3.Value from diagonal + match/mismatch scores.
Dynamic Programming Approach

https://www.youtube.com/watch?v=ipp-pNRIp4g
Dynamic Programming Approach
Steps of Alignment:
1. Initialization.
2. Matrix filling.
3. Alignment.
Rules:
● 1st column and 1st row must be blank.
●1+M×1+N
● After 0 add the Progressive gap penalties.
● Fill the other boxes as: take the three values for
each box & Select the greater value.
1.Value from left + gap penalty
2.Value from top +gap penalty
3.Value from diagonal + match/mismatch scores.
Example #1
Sequence #1 AAAC
Sequence #2 AGC
Match = 1, Mismatch = - 1, Gap penalty = - 2.
A A A C

0 -2 -4 -6 -8

A -2 1 -1 -3 -5

G -4 -1 0 -2 -4

C -6 -3 -2 -1 -1
Example #1
Sequence #1 AAAC
Sequence #2 AGC
Match = 1, Mismatch = - 1, Gap penalty = - 2.
Trace back the arrows.
Trace back the values from right bottom corner
towards the left starting point.

Match: diagonal movement.


T

-3 2

T -1 1

Mismatch : towards the greater value. 0 -2

A 1 -1
How to align the sequence?

○ Start the alignment from right to left.


○ Match = If the diagonal arrow is from larger
to smaller value.
○ Mismatch = if the diagonal arrow is from
smaller to larger value.
○ Gap = if the arrow moves vertically or
horizontally.
Alignment:
AAAC
AG_C
Match = 2
Mismatch = - 1
Gap penalty = - 1
Alignment score = 0
Example #2

Sequence # 1 ATGCGT
Sequence # 2 ACGGCGT
A C G G C G T
0 -2 -4 -6 -8 -10 -12 -14
A -2 1 -1 -3 -5 -7 -9 -11
T -4 -1 0 -2 -4 -6 -8 -8
G -6 -3 -2 1 -1 -3 -5 -7
C -8 -5 -2 -1 0 0 -2 -4
G -10 -7 -4 -1 0 -1 1 -1
T -12 -9 -6 -3 -2 -1 -1 2
Alignment :
ACGGCGT
AT_GCGT

Match = 5
Mismatch = - 1
Gap penalty = - 1
Alignment score = 3
Dynamic Programming Approach
Dynamic Programming Approach
Dynamic Programming Approach
Dynamic Programming Approach
Dynamic Programming Approach

You might also like