java - 序列比对中的动态规划填充矩阵

Question

大家好，我有 2d 字符数组 opt[][]，我的数组中有 2 个序列，如示例所示

我的

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

和

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

我目前有这个输出

   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

我的问题是如何使用动态编程

将此数组创建到此

/image/ViHc9.png

如果是一场比赛 0 罚分如果不匹配 1 罚分如果有差距，则罚 2 分

我可以像这样比较我的数组的字符

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

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

                    result[0][i] =1;

                }

但这只是我所做的一个简单测试，看看我是否可以进行比较，结果证明我可以。

我怎样才能从这里到那里(到图片数组

Answer 1

我建议您阅读这些文章。

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

任何语言的实现都非常简单。

如果您需要有关动态规划的一般信息，
要么自己 Google 一下，要么检查这两个链接。

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