Question

Consider two homologous DNA sequences, GATTC and CCATG. Use the Needleman-Wunsch algorithm to find the optimal global alignment between these two sequences. Use a linear gap penalty of -4 and the substitution matrix provided below. The dynamic programming matrix is already outlined below, you just need to fill it according to the algorithm. Be sure to write out your final alignment!

substitution matrix A C GT A 10 -5 0 -5 C -5 10 -5 0 G 0 -5 10 -5 T -5 0 5 10 gaps = -4

Answer 1

here we use two matrix one is score matrix and other is trace back matrix

with the help of score matrix we fill trace back matrix and with the trace back matrix we find best optimal global alignment

given sequence is GATTC and CCATG

we make both matrix for the given sequence

score matrix

		G	A	T	T	C
	0
C
C
A
T
G

since gap =-4

fill first row and first column by keep adding gap each time with start at 0.

so now score matrix is

		G	A	T	T	C
	0	-4	-8	-12	-16	-20
C	-4
C	-8
A	-12
T	-16
G	-20

for filling other box of matrix use following Dynamic Programming formula

$D(i,j)=max\left\{\begin{matrix} D(i-1,j-1)+S(X_i,Y_j) & & \\ D(i-1,j)+gap& & \\ D(i,j-1)+gap& & \end{matrix}\right.$

where S(Xi,Yj) is the substitution score for residue i,j

we fill matrix accordingly

		G	A	T	T	C
	0	-4	-8	-12	-16	-20
C	-4	-5
C	-8
A	-12
T	-16
G	-20

look at how come highlighed entry

D(1,1) = max{ D(0,0)+S(C,G), D(0,1)+gap, D(1,0)+gap }

look at matrix D(0,0) =0 , D(0,1) = -4 , D(1,0) = -4 and from substitution matrix which is given in question look entry for S(C,G) = -5

now D(1,1) = max{ 0-5 , -4-4 ,-4-4} =max{-5, -8, -8} = -5

since this entry come from diagonal so fill tace back matrix with diagonal

	G	A	T	T	C
C	dia
C
A
T
G

trace back entry tell us corresponding score matrix come from diagonal or up or left so it is useful for find optimize global alignment

similarly fill score matrix enty and corresponding entry

score matrix

		G	A	T	T	C
	0	-4	-8	-12	-16	-20
C	-4	-5	-9	-8	-12	-6
C	-8	-9	-10	-9	-8	-2
A	-12	-8	1	-3	-8	-6
T	-16	-12	-3	11	7	3
G	-20	-6	-7	7	6	2

trace back matrix

	G	A	T	T	C
C	dia	dia/left	dia	dia/left	dia
C	dia/up	dia	dia	dia	dia
A	dia	dia	left	left	up
T	up	up	dia	dia/left	left
G	dia	up	up	dia	dia/left

now look one more highlighted entry

look at how come highlighed entry

D(5,5) = max{ D(4,4)+S(C,G), D(5,4)+gap, D(4,5)+gap }

look at matrix D(4,4) =7 , D(4,5) = 3 , D(5,4) = 6 and from substitution matrix which is given in question look entry for S(G,C) = -5

now D(5,5) = max{ 7-5 , 6-4 ,3-4} =max{2, 2, -1} = 2

since this entry come from diagonal and left so fill tace back matrix with diagonal

similarly we fill whole matrix

now trace traceback matrix from right bottom index and trace it path

since right bottom entry is dia/left so we move both path let's suppose we move diagonal up means 4th row and 4th column which again has diagonal/left entry suppose we move diagonal up means 3rd row and 3rd column which has left so we move left then we are 3rd row and 2nd column which has entry as diagonal now we have 2nd row and first column which has entry diagonal and up suppose we move up so our tracing is complete...

look at trace back highlighed entry

trace back matrix

	G	A	T	T	C
C	dia	dia/left	dia	dia/left	dia
C	dia/up	dia	dia	dia	dia
A	dia	dia	left	left	up
T	up	up	dia	dia/left	left
G	dia	up	up	dia	dia/left

so sequence is CAATG(row) and GATTC (column) entry which is global alignment .

similarly explore all entryu from trace back matrix...

	G	A	T	T	C
C	dia	dia/left	dia	dia/left	dia
C	dia/up	dia	dia	dia	dia
A	dia	dia	left	left	up
T	up	up	dia	dia/left	left
G	dia	up	up	dia	dia/left

so sequence is CCAATG(row) and GGATTC (column) entry which is global alignment .

and

	G	A	T	T	C
C	dia	dia/left	dia	dia/left	dia
C	dia/up	dia	dia	dia	dia
A	dia	dia	left	left	up
T	up	up	dia	dia/left	left
G	dia	up	up	dia	dia/left

so sequence is CATTG(row) and GATTC (column) entry which is global alignment .

and

	G	A	T	T	C
C	dia	dia/left	dia	dia/left	dia
C	dia/up	dia	dia	dia	dia
A	dia	dia	left	left	up
T	up	up	dia	dia/left	left
G	dia	up	up	dia	dia/left

so sequence is CCATTG(row) and GGATTC (column) entry which is global alignment .

and

	G	A	T	T	C
C	dia	dia/left	dia	dia/left	dia
C	dia/up	dia	dia	dia	dia
A	dia	dia	left	left	up
T	up	up	dia	dia/left	left
G	dia	up	up	dia	dia/left

so sequence is CATGG(row) and GATTC (column) entry which is global alignment

and

	G	A	T	T	C
C	dia	dia/left	dia	dia/left	dia
C	dia/up	dia	dia	dia	dia
A	dia	dia	left	left	up
T	up	up	dia	dia/left	left
G	dia	up	up	dia	dia/left

so sequence is CCATGG(row) and GGATTC (column) entry which is global alignment .