глобальное выравнивание последовательностей динамическое программирование нахождение минимума в матрице

Question

У меня есть 2 последовательности, AACAGTTACC и TAAGGTCA, и я пытаюсь найти глобальное выравнивание последовательностей. Мне удалось создать 2D-массив и создать матрицу, и я даже заполнил ее полудинамическим подходом.

Вот мой код, чтобы заполнить матрицу:

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 

Но я хочу, чтобы это выглядело, как это (мне все равно это номера в изображениях):

Я иду t для применения штрафных санкций: за несоответствие 1 и за пробел 2, если его совпадение 0.

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

(The SubsetMapping возвращается в основном, простой структурой, что дает индекс для обоих контекстов, https://github.com/Pomax/DOM-diff/blob/rewrite/rewrite/rewrite.html#L52)