固定长度子串的最长公共子序列

Question

固定长度子串的最长公共子序列

3

我一直在使用最长公共子序列（LCS）来查找序列之间的相似性。以下动态规划代码计算答案。

def lcs(a, b):
    lengths = [[0 for j in range(len(b)+1)] for i in range(len(a)+1)]
    # row 0 and column 0 are initialized to 0 already
    for i, x in enumerate(a):
        for j, y in enumerate(b):
            if x == y:
                lengths[i+1][j+1] = lengths[i][j] + 1
            else:
                lengths[i+1][j+1] = \
                    max(lengths[i+1][j], lengths[i][j+1])
    # read the substring out from the matrix
    result = ""
    x, y = len(a), len(b)
    while x != 0 and y != 0:
        if lengths[x][y] == lengths[x-1][y]:
            x -= 1
        elif lengths[x][y] == lengths[x][y-1]:
            y -= 1
        else:
            assert a[x-1] == b[y-1]
            result = a[x-1] + result
            x -= 1
            y -= 1
    return result

然而，我意识到我真正想解决的问题有些不同。给定一个固定的 k，我需要确保公共子序列仅涉及长度恰好为 k 的子字符串。例如，设 k = 2，让这两个字符串为

A = "abcbabab"
B = "baababcc"

我需要的子序列是 "ba"+"ab" = baab。

是否可以修改动态规划解决方案来解决这个问题？

原始的最长公共子序列问题只是 k=1 的情况。 一个不起作用的方法。 如果我们执行上面的LCS算法，我们可以从动态规划表中得到对齐，并检查这些符号是否出现在两个输入序列的长度为k的非重叠子字符串中，如果没有，则删除它们。问题是这并不能给出最优解。

- Simd

“k”的规模是多少？我的直觉告诉我解决方案在“k”方面会呈指数级增长，但我对这个说法没有任何证据。 - amit

@amit k可以达到n。我觉得基于动态规划的O(n^2)解决方案应该存在，但我还没有想出来。 - Simd

对于 aaa，当 k=2 时，最长子序列应该是 aa，对吗？（如果不是，那么在 aaa_bc_bc 和 bc:bc:aaa 中最长的序列是什么？） - amit

@amit aaa，k=2时最长子序列为aa，正如你所说的。是的。 - Simd

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

纠正基本上是当相关索引中的两个字符串有匹配的子字符串时（而不是现在的匹配字母）。

想法是，不仅仅在原始解决方案中检查大小为1的子字符串，而是检查长度为k的子字符串，并将解决方案加1（并且在字符串中“跳”k）。

递归方法的公式应该转换为DP解决方案：

f(i,0) = 0
f(0,j) = 0
f(i,j) = max{
          f(i-k,j-k) + aux(s1,s2,i,j,k)
          f(i-1,j)
          f(i,j-1)
             }

aux(s1,s2,i,j,k)是一个函数，旨在检查两个子字符串是否匹配，定义如下：

aux(s1,s2,i,j,k) = 1         | if s1.substring(i-k,i) equals s2.substring(j-k, j)
                   -infinity | otherwise

您可以使用标记max{}的辅助矩阵稍后重构对齐，并在矩阵完成后从后往前进行。

示例：

bcbac 和 cbcba。 k=2

f生成的矩阵：

      c   b   c  b   a
   0  0   0   0  0   0
b  0  0   0   0  0   0
c  0  0   0   1  1   1   
b  0  0   1   1  1   1
a  0  0   1   1  1   2
c  0  0   1   1  1   2

为了重现对齐，您需要生成'choices'矩阵：

1 - 选择 f(i-k,j-k) + aux(s1,s2,i,j,k)
2 - 选择 f(i-1,j)
3 - 选择 f(i,j-1)
d - 不考虑 (所有选择都可以)
x/y - 表示 x 或 y 中的一个。

c      b      c     b      a

b   2/3    2/3    2/3   2/3    2/3
c   2/3    2/3     1     2      2   
b   2/3     3     2/3    d     2/3
a   2/3     3     2/3   2/3     1
c   2/3     3     2/3   2/3     3

现在，重构对齐 - 从最后一个（右下角）单元格开始：

它是“3” - 向上移动，不将任何内容添加到对齐中。
它是1 - 我们需要将'ba'添加到对齐中。（当前对齐 ='ba'）。向上和左移k。
它是1，在对齐中加入'bc'。当前的对齐：'bcba'。向上和左移k。
它是2/3 - 向左或向上移动。

重构时访问的顺序为：（0表示-未访问，许多单元格中的数字表示其中任何一个都可以）。

      c   b   c  b   a
   0  4   0   0  0   0
b  4  3   0   0  0   0
c  0  0   0   0  0   0   
b  0  0   0   2  0   0
a  0  0   0   0  0   0
c  0  0   0   0  0   1