0

我正在尝试使用 needleman 解决“最长公共子序列”问题。

示例：输入：text1 = "abcde", text2 = "ace" 输出：3
解释：最长的公共子序列是 "ace"，它的长度是 3。

对于 text1 =“ezu”和 text2 =“ubm”的情况，我对算法应该如何工作感到非常困惑。

Needleman 矩阵是（假设不匹配的成本是 -3，差距的成本是 -4 和匹配是 1）：

X - 你 b 米
- 0 -4 -8 -12
e -4 -3 -7 -11
z -8 -7 -6 -10
你 -12 -7 -10 -9

现在算法状态从矩阵的底角回溯，并且：

  • 如果 text[i] == text[j] => 向上移动对角线
  • 否则移动到上下之间的最大值。

因此，从 -9 开始，我必须在 -10 和 -10 之间进行选择（我应该向上还是向下？），无论做出何种决定，我都不会遇到这种情况 [i,j] = [3,1]

我的代码：

int longestCommonSubsequence(string text1, string text2) {
        
        int m = text1.length();
        int n = text2.length();
        
        vector<vector<int>> vec(m+1, vector(n+1,0));
        int mismatch  = -3;
        int gap = -4;
        int match = 1;
        
        for (int i = 1; i <= m; i++) {
            vec[i][0] = vec[i-1][0] + gap;
        }
        
        for (int i = 1; i <= n; i++) {
            vec[0][i] = vec[0][i-1] + gap;
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int cost = 0;
                if (text1[i-1] != text2[j-1]) {
                    cost = max(vec[i-1][j-1]+ mismatch, min(vec[i-1][j]+gap, vec[i][j-1]+gap));
                }  else {
                    cost = match  + vec[i-1][j-1];
                }
                vec[i][j] = cost;
            }
        }
        
        int matchLen = 0;
        
        int i = m;
        int j = n;
        
        while (i >0 && j >0) {
            
            if (text1[i-1] == text2[j-1]) {
                matchLen++;
                i--;
                j--;
            } else if (i > 0 && j > 0) {
                
                if (vec[i-1][j] > vec[i][j-1]) {
                    i--;
                } else {
                    
                    j--;
                }
            } else {
                break;
            }
            
        }
        
        return matchLen;
        
    }

谢谢！

4

1 回答 1

3

Needle 矩阵的每个单元格实际上显示了在对齐两个序列时哪个动作被认为是最佳的：

  • 从两个序列中插入一个字母，从而沿对角线移动（匹配或不匹配）
  • 插入一个序列中的一个字母和一个间隙而不是另一个，从而垂直或水平移动

根据您分配给不匹配（-3）和间隙（-4）的罚分以及您给匹配（1）的分数，您获得匹配的唯一方法（长度=1）：

e z u _ _

_ _ u b m

将得到：gap(-4) + gap(-4) + match(1) + gap(-4) + gap(-4) = -15

并且算法将选择最高分数对齐（如果您的代码是正确的，那现在不正确，因为您没有实现不匹配选择并且已经考虑到它分配分数），这是完全不匹配的：

e z u

u b m

将得到：不匹配（-3）+不匹配（-3）+不匹配（-3）=-9

如果您希望在选定的序列中发生匹配，您应该考虑平衡您的评分系统。

于 2021-07-12T06:35:42.980 回答