动态规划-古生物DNA序列血缘分析

问题描述

DNA 是由 A、C、G、T 四种核苷酸组成，例如AAAGTCTGAC，假定自然环境下 DNA 发生异变的情况有：

1. 基因缺失一个核苷酸
2. 基因新增一个核苷酸
3. 基因替换一个核苷酸

且发生概率相同。

古生物学家 Sam 得到了若干条相似 DNA 序列，Sam 认为一个 DNA 序列向另外一个 DNA 序列转变所需的最小异变情况数可以代表其物种血缘相近程度，异变情况数越少，血缘越相近，请帮助 Sam 实现获取两条 DNA 序列的最小异变情况数的算法。

输入格式

每个样例只有一行，两个 DNA 序列字符串以英文逗号“,”分割

输出格式

输出转变所需的最少情况数，类型是数字

输入样例：

• AGT,AGCT

输出样例：

• 1

数据范围：
每个 DNA 序列不超过 100 个字符

动态规划（Dynamic Programming, DP）是一种通过将问题分解为子问题并存储子问题的解来解决复杂问题的方法。在这个问题中，我们可以使用动态规划来计算将一个DNA序列转换为另一个DNA序列所需的最小操作数。

问题理解

我们需要计算两个DNA序列之间的最小编辑距离（Edit Distance），即从一个序列转换到另一个序列所需的最小操作数。操作包括：

1. 插入一个核苷酸
2. 删除一个核苷酸
3. 替换一个核苷酸

动态规划的应用

我们可以定义一个二维数组 dp，其中 dp[i][j] 表示将 dna1 的前 i 个字符转换为 dna2 的前 j 个字符所需的最小操作数。

状态转移方程

1. 初始化：

   • 如果 dna1 为空，那么将 dna1 转换为 dna2 需要插入 dna2 的所有字符。
   • 如果 dna2 为空，那么将 dna1 转换为 dna2 需要删除 dna1 的所有字符。

2. 状态转移：

   • 如果 dna1[i-1] == dna2[j-1]，那么 dp[i][j] = dp[i-1][j-1]，因为不需要任何操作。
   • 否则，dp[i][j] 可以从以下三种操作中选择最小值：
     • 插入操作：dp[i][j-1] + 1
     • 删除操作：dp[i-1][j] + 1
     • 替换操作：dp[i-1][j-1] + 1

算法步骤

1. **创建二维数组 dp**：大小为 (m+1) x (n+1)，其中 m 和 n 分别是 dna1 和 dna2 的长度。
2. 初始化边界条件：
   • dp[i][0] = i 表示将 dna1 的前 i 个字符转换为空字符串需要删除 i 个字符。
   • dp[0][j] = j 表示将空字符串转换为 dna2 的前 j 个字符需要插入 j 个字符。
3. 填充 dp 数组：
   • 使用双重循环遍历 dp 数组，根据状态转移方程更新 dp[i][j]。
4. 返回最终结果：dp[m][n] 即为将 dna1 转换为 dna2 所需的最小操作数。

代码实现：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int solution(std::string dna1, std::string dna2) {
    int m = dna1.size();
    int n = dna2.size();
    
    // 创建一个 (m+1) x (n+1) 的二维数组 dp
    std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
    
    // 初始化 dp 数组
    for (int i = 0; i <= m; ++i) {
        dp[i][0] = i;  // 将 dna1 的前 i 个字符转换为空字符串，需要删除 i 个字符
    }
    for (int j = 0; j <= n; ++j) {
        dp[0][j] = j;  // 将空字符串转换为 dna2 的前 j 个字符，需要插入 j 个字符
    }
    
    // 填充 dp 数组
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dna1[i-1] == dna2[j-1]) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = std::min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
            }
        }
    }
    
    // 返回最终结果
    return dp[m][n];
}

int main() {
    std::cout << (solution("AGT", "AGCT") == 1) << std::endl;
    std::cout << (solution("", "ACGT") == 4) << std::endl;
    std::cout << (solution("GCTAGCAT", "ACGT") == 5) << std::endl;
    return 0;
}

总结：

通过动态规划，我们可以有效地计算出将一个DNA序列转换为另一个DNA序列所需的最小操作数。这个方法的时间复杂度为 O(m * n)，其中 m 和 n 分别是两个序列的长度。