java - 具有最大间隙长度 3 的全局成对序列比对

Question

我正在尝试使用线性缺口罚分对两个序列进行全局比对。到目前为止，问题很简单。但是，最大允许间隙长度为 3。例如，

ACDDAB

AA---BB

是允许的，但是

A----B

ADCCCB 是不允许的。

我的问题是如何为这个问题构造递推关系。我是一名分子生物学大四学生，我正在按照教授的建议参加生物信息学类(class)，所以我对 DP 没有任何经验，也不知道如何实现目标。我将不胜感激任何线索或帮助。

Answer 1

根据我从问题中了解到的情况，这可能会有所帮助。如果此伪代码有问题，请告诉我:)

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]; 
    }
}