string - 在 O(mn) 中解决字符串对齐问题

Question

我需要用 O(nm) 解决以下问题。n = |T| 米 = |P| 其中 T,P 两个字符串 f 是一个评分函数。

该算法应返回 T 的子字符串 T'，使得 score(P,T') 值为最大值。

score(A,B) 是根据 f 对齐 A 和 B 的最大值。

我知道如果 f 是离散的（意味着矩阵的对角线的权重不大于常数 C，水平和垂直边缘为 0 或其他常数），我可以从 DIST 矩阵中得到它，该矩阵是 Monge 矩阵，但在这种情况下， f 是从 (sigma * {-})x(sigma * {-}) 到 R 的一般函数（其中 '-' 是一个间隙）。

有任何想法吗？

Answer 1

您已经注意到有几种算法可以计算图中的最短路径，其弧是 (i, j) → (i + 1, j), (i + 1, j + 1), (i, j + 1 ）。该算法的最一般形式是允许单独指定每个弧长，具有以下含义。

• (i, j) → (i + 1, j)：将 P 的第 (i+1) 个字母与 T 中的间隙对齐的成本
• (i, j) → (i + 1, j + 1)：将 P 的第 (i+1) 个字母与 T 的第 (j+1) 个字母对齐的成本
• (i, j) → (i, j + 1)：将 P 中的间隙与 T 的第 (j+1) 个字母对齐的成本

成本可以是负数。为了解决您的子字符串问题，使所有 (i, j) → (i, j + 1) 弧的成本为零，以便我们可以从 T 中删除而不会受到惩罚。