dynamic programming filling matrix in sequence alignment

Question

hello guys i have 2d char array opt[][] and i have 2 sequence in my arrays like in example

my

 `opt[0][0]=A        
  opt[0][1]=T
  opt[0][2]=G
  opt[0][3]=A`   

and

 opt[1][0]=A
 opt[2][0]=G
 opt[3][0]=C
 opt[4][0]=T

i have this output currently

   x/y|  A  T  G  A  -
_______________________
  0 A |  0  0  0  0
  1 G |  0  0  0  0
  2 C |  0  0  0  0
  3 T |  0  0  0  0
  4 - |  0  0  0  0

my problem is this how can i use dynamic programming

to create this array into this

https://i.stack.imgur.com/ViHc9.png

if its a match 0 penalty if its a mismatch 1 penalty if its a gap its 2 penalty

i can compare chars of my array like this

for(int i=0;i<4;i++){

                if(opt[0][i]==opt[i+1][0]){

                    result[0][i] =1;

                }

but this is just a simple test i made to see if i can compare and it turned out i can.

how can i go from here to there(to the picture array

Answer 1

I suggest you read these articles.

http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm
http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm

The implementation in any language is pretty trivial.

And if you need information about dynamic programming in general,
either Google for it yourself, or check these two links.

http://en.wikipedia.org/wiki/Dynamic_programming
https://www.topcoder.com/tc?d1=tutorials&d2=dynProg&module=Static