[ICPC 2001 Taejon R] 相似基因

题意

给出两条只包含 A/C/G/T 的基因序列。

可以在任意位置插入空位 -，把两条序列拉齐。每一列根据题目给定的打分表计算得分，总分最大的那种对齐方式就是答案。

思路

最直接的想法是从左到右递归枚举当前这一列怎么对齐。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#include <bits/stdc++.h>
using namespace std;

// brute.cpp：暴力递归枚举当前位置三种对齐方式。

const int NEG_INF = -1000000000;

int n, m;
string a, b;
int score[5][5] = {
    {5, -1, -2, -1, -3},
    {-1, 5, -3, -2, -4},
    {-2, -3, 5, -2, -2},
    {-1, -2, -2, 5, -1},
    {-3, -4, -2, -1, 0}
};

int id(char ch) {
    if (ch == 'A') return 0;
    if (ch == 'C') return 1;
    if (ch == 'G') return 2;
    if (ch == 'T') return 3;
    return 4;
}

int dfs(int i, int j) {
    if (i > n && j > m) {
        return 0;
    }

    int best = NEG_INF;

    if (i <= n && j <= m) {
        best = max(best, dfs(i + 1, j + 1) + score[id(a[i])][id(b[j])]);
    }
    if (i <= n) {
        best = max(best, dfs(i + 1, j) + score[id(a[i])][4]);
    }
    if (j <= m) {
        best = max(best, dfs(i, j + 1) + score[4][id(b[j])]);
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> a;
    cin >> m >> b;

    a = " " + a;
    b = " " + b;

    cout << dfs(1, 1) << '\n';
    return 0;
}

在 brute.cpp 里，每一步只有三种可能：

当前两个字符直接对齐
第一条序列当前字符和 - 对齐
第二条序列当前字符和 - 对齐

这个递归非常贴近题意，但会重复计算很多相同的 (i,j) 状态。

于是把它改成二维 DP。

设：

dp[i][j] = 第一条序列前 i 个字符和第二条序列前 j 个字符的最大相似度

那么最后一列只有三种来源：

a[i] 对 b[j]
dp[i-1][j-1] + score(a[i], b[j])
a[i] 对 -
dp[i-1][j] + score(a[i], '-')
- 对 b[j]
dp[i][j-1] + score('-', b[j])

取三者最大值即可。

状态表

以样例前缀为例，下面这张表展示部分状态值：

`i \\ j`	0	1(`G`)	2(`T`)
0	0	-2	-3
1(`A`)	-3	-1	-3
2(`G`)	-5	2	-1

这张表的含义是：

第一行表示第一条序列为空，只能让第二条序列不断和 - 对齐
第一列同理
中间位置则来自三种转移的最大值

整个表填完后，右下角 dp[n][m] 就是最终答案。

DP 公式

设 $dp_{i,j}$ 表示第一条序列前 $i$ 个字符和第二条序列前 $j$ 个字符的最大相似度。转移来自三种选择：

dp_{i,j}=\max\left\{ \begin{aligned} &dp_{i-1,j-1}+score(a_i,b_j),\\ &dp_{i-1,j}+score(a_i,-),\\ &dp_{i,j-1}+score(-,b_j) \end{aligned} \right\}

边界为只和空位匹配：

dp_{i,0}=dp_{i-1,0}+score(a_i,-),\quad dp_{0,j}=dp_{0,j-1}+score(-,b_j)

最终答案是：

dp_{n,m}

公式解释：序列比对的最后一步只有三种：两个字符互相匹配，第一条字符和空位匹配，或第二条字符和空位匹配。分别对应三个前驱状态，取相似度最大的方案。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int NEG_INF = -1000000000;

int n, m;
string a, b;
int score[5][5] = {
    {5, -1, -2, -1, -3},
    {-1, 5, -3, -2, -4},
    {-2, -3, 5, -2, -2},
    {-1, -2, -2, 5, -1},
    {-3, -4, -2, -1, 0}
};
int dp[MAXN][MAXN];

int id(char ch) {
    if (ch == 'A') return 0;
    if (ch == 'C') return 1;
    if (ch == 'G') return 2;
    if (ch == 'T') return 3;
    return 4;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> a;
    cin >> m >> b;

    a = " " + a;
    b = " " + b;

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = NEG_INF;
        }
    }

    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i - 1][0] + score[id(a[i])][4];
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = dp[0][j - 1] + score[4][id(b[j])];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // 1. a[i] 和 b[j] 对齐
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + score[id(a[i])][id(b[j])]);

            // 2. a[i] 和 '-' 对齐
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + score[id(a[i])][4]);

            // 3. '-' 和 b[j] 对齐
            dp[i][j] = max(dp[i][j], dp[i][j - 1] + score[4][id(b[j])]);
        }
    }

    cout << dp[n][m] << '\n';
    return 0;
}

复杂度

时间复杂度： $O(nm)$
空间复杂度： $O(nm)$

总结

这题本质上是经典的序列对齐 DP。

关键在于看出“最后一列怎么对齐”只有三种情况，然后自然写出二维转移。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。