当矩阵值相同时，Needleman 算法不起作用

Question

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

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

我对算法在 text1 = "ezu" 和 text2 = "ubm" 的情况下应该如何工作感到非常困惑。

Needleman 矩阵为（假设不匹配成本为 -3，间隙成本为 -4，匹配为 1）：

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

现在算法声明从矩阵的底角回溯并且：

if text[i] == text[j] => 向上移动对角线
else移动到上下之间的最大值

因此从 -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;
        
    }

谢谢！

Answer 1

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

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

基于您分配给不匹配 (-3) 和差距 (-4) 的罚分和你给匹配的分数 (1)，你获得匹配的唯一方法 (长度 =1):

e z u _ _

_ _ u b m

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

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

e z u

u b m

将得到：不匹配(-3) + 不匹配(-3) + 不匹配(-3) = -9

如果您想在 selected 序列中进行匹配，您应该考虑平衡您的分数系统。

当矩阵值相同时，Needleman 算法不起作用

Needleman algorithm not working when matrix values are the same

c++

needleman-wunsch