全局序列比對動態規劃在矩陣中找到最小值

Question

我有2個序列，AACAGTTACC和TAAGGTCA，我試圖找到一個全局序列比對。我設法創建了二維數組並創建了矩陣，我甚至用半動態方法填充了它。

這裏是我的代碼來填充矩陣：

void process() { 
    for (int i = 1; i <= sequenceA.length; i++) { 
     for (int j = 1; j <= sequenceB.length; j++) { 
      int scoreDiag = opt[i-1][j-1] + equal(i, j); 
      int scoreLeft = opt[i][j-1] - 1; 
      int scoreUp = opt[i-1][j] - 1; 
      opt[i][j] = Math.max(Math.max(scoreDiag, scoreLeft), scoreUp); 
     } 
    } 
} 

private int equal(int i, int j) { 
    if (sequenceA[i - 1] == sequenceB[j - 1]) { 
     return 1; 
    } else { 
     return -1; 
    } 
} 

我的主要問題是，這個代碼生成的輸出：

0 -1 -2 -3 -4 -5 -6 -7 -8  
-1 -1 0 -1 -2 -3 -4 -5 -6  
-2 -2 0 1 0 -1 -2 -3 -4  
-3 -3 -1 0 0 -1 -2 -1 -2  
-4 -4 -2 0 -1 -1 -2 -2 0  
-5 -5 -3 -1 1 0 -1 -2 -1  
-6 -4 -4 -2 0 0 1 0 -1  
-7 -5 -5 -3 -1 -1 1 0 -1  
-8 -6 -4 -4 -2 -2 0 0 1  
-9 -7 -5 -5 -3 -3 -1 1 0  
-10 -8 -6 -6 -4 -4 -2 0 0 

但我希望它看起來像這樣（我都不在乎在照片的序號）：

我去如果其匹配爲0，則應用罰分：每個不匹配1和每個差距2.

Answer 1

還有，你需要修改幾件事情：

1. 請注意，在圖像中，您給我們的是從右下角到左上角的對齊方式。所以在這張圖片中，他們並不是真正對齊AACAGTTACC和TAAGGTCA，而是CCATTGACAA和ACTGGAAT。
2. 你說你想global alignment，但你實際上計算local alignment。主要區別在於序列開始時的處罰。在全局比對中，必須計算第一行和第一列的插入和刪除。
3. 第三，您沒有正確應用您提到的處罰。相反，你總是使用-1來懲罰並使用+1來獎勵。
4. 在示例圖片中，他們沒有在每個位置取最大值，但是最小值（這是因爲您的懲罰是積極的，獎勵是0，而不是其他方式，所以您希望最小化值）。

完整的解決方案是：

// Note that these sequences are reversed! 
String sequenceA ="CCATTGACAA"; 
String sequenceB = "ACTGGAAT"; 

// The penalties to apply 
int gap = 2, substitution = 1, match = 0; 

int[][] opt = new int[sequenceA.length() + 1][sequenceB.length() + 1]; 

// First of all, compute insertions and deletions at 1st row/column 
for (int i = 1; i <= sequenceA.length(); i++) 
    opt[i][0] = opt[i - 1][0] + gap; 
for (int j = 1; j <= sequenceB.length(); j++) 
    opt[0][j] = opt[0][j - 1] + gap; 

for (int i = 1; i <= sequenceA.length(); i++) { 
    for (int j = 1; j <= sequenceB.length(); j++) { 
     int scoreDiag = opt[i - 1][j - 1] + 
       (sequenceA.charAt(i-1) == sequenceB.charAt(j-1) ? 
        match : // same symbol 
        substitution); // different symbol 
     int scoreLeft = opt[i][j - 1] + gap; // insertion 
     int scoreUp = opt[i - 1][j] + gap; // deletion 
     // we take the minimum 
     opt[i][j] = Math.min(Math.min(scoreDiag, scoreLeft), scoreUp); 
    } 
} 

for (int i = 0; i <= sequenceA.length(); i++) { 
    for (int j = 0; j <= sequenceB.length(); j++) 
     System.out.print(opt[i][j] + "\t"); 
    System.out.println(); 
} 

的結果是一樣的，你給我們的例子中（但反轉，切記！）：

0 2 4 6 8 10 12 14 16 
2 1 2 4 6 8 10 12 14 
4 3 1 3 5 7 9 11 13 
6 4 3 2 4 6 7 9 11 
8 6 5 3 3 5 7 8 9 
10 8 7 5 4 4 6 8 8 
12 10 9 7 5 4 5 7 9 
14 12 11 9 7 6 4 5 7 
16 14 12 11 9 8 6 5 6 
18 16 14 13 11 10 8 6 6 
20 18 16 15 13 12 10 8 7 

所以最終的比對得分是發現在opt[sequenceA.length()][sequenceB.length()]（7）。如果您確實需要顯示圖像中的逆矩陣，請執行以下操作：

for (int i = sequenceA.length(); i >=0; i--) { 
    for (int j = sequenceB.length(); j >= 0 ; j--) 
     System.out.print(opt[i][j] + "\t"); 
    System.out.println(); 
} 

Answer 2

看看http://en.wikipedia.org/wiki/Longest_common_substring，代碼幾乎可以複製粘貼多種語言，並且很容易適應也可以告訴你對齊指數。我不得不做類似的事情，並結束了與https://github.com/Pomax/DOM-diff/blob/rewrite/rewrite/rewrite.html#L103

（它返回SubsetMapping基本上是一個簡單的結構，讓兩個環境指標，https://github.com/Pomax/DOM-diff/blob/rewrite/rewrite/rewrite.html#L52）