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

Я пытаюсь глобально выровнять две последовательности с линейным штрафом за разрыв. Проблема прямолинейна до сих пор. Однако максимально допустимая длина промежутка равна 3. Например,

АКДДАББ

AA---BB

разрешено, но

A----B

ADCCCB не допускается.

Мой вопрос в том, как я могу построить рекуррентное отношение для этой проблемы. Я старший специалист по молекулярной биологии и, как предложил мой профессор, посещаю курс биоинформатики, поэтому у меня нет ни опыта работы с DP, ни представления о том, как достичь цели. Буду признателен за любую подсказку или помощь.


java sequence algorithm bioinformatics dynamic-programming
person Osman Yildiz    schedule 01.04.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Насколько я понимаю из вопроса, это может быть полезно. Если есть какие-то проблемы с этим псевдокодом, дайте мне знать :)

seq1 = AABB
seq2 = ACDDABB



len1 = length of seq1
len2 = length of seq2
// 0-indexed arrays
dp[0..len1-1][0..len2-1][0..3] = -1;
bool solve ( char seq1[], char seq2[], int i1, int i2, int lim) {
    if (i1 == len1-1) { // First sequence is finished
        if (len2-1-i2 <= 3-lim) return true; // If number of characters in second sequence are less than limit left
        return false;
    }
    // If we already know what happens for these indexes and limit
    if (dp[i1][i2][lim] != -1) return dp[i1][i2][lim];
    if (seq1[i1] == seq2[i2]) { // Ok
        dp[i1][i2][lim] = solve(seq1, seq2, i1+1, i2+1, lim); // Check for next character
        return dp[i1][i2][lim];
    }
    else { 
        // Maximum allowed limit is 3, so skip characters accordingly
        bool r1,r2,r3;
        r1 = r2 = r3 = false;
        if (lim < 3)
            r1 = solve(seq1, seq2, i1, i2+1, lim+1); // One char skipped in second seq.
        if (lim < 2) 
            r2 = solve(seq1, seq2, i1, i2+2, lim+2); // Two char skipped in second seq.
        if (lim < 1)
            r3 = solve(seq1, seq2, i1, i2+3, lim+3); // Three char skipped in second seq.
        dp[i1][i2][lim] = r1 || r2 || r3; // If any of them is true, then it matches
        return dp[i1][i2][lim]; 
    }
}
person Priyank Bhatnagar    schedule 02.04.2012
comment
Я использовал ваш подход, чтобы закончить, это сработало как шарм :) Спасибо. - person Osman Yildiz; 04.04.2012
comment
@OsmanYildiz, я рад, что это помогло. Спасибо за хорошую проблему! :) - person Priyank Bhatnagar; 04.04.2012