Answer to Question #176052 in Bioinformatics for Tulika

Question

Calculate the dynamic programming matrix and the optimal local and global alignment for the DNA sequences

a: GAATTC and b: GATTA,

scoring +2 for a match,

-1 for a mismatch,

and using a linear gap penalty function W(L) = -2L

Answer 1

Algorithm 3: Longest common substring.

LCS(x, y)

(1) Initialization:

(2) D(0, 0) = 0.

(3) for i = 1 to M

(4) D(i, 0) = 0.

(5) for j = 1 to N

(6) D(0, j) = 0.

(7) Recursion:

(8) for i = 1 to M

(9) for j = 1 to N

(10) if xi = yj

(11) D(i, j) ← D(i − 1, j − 1) + 1