题解 | #基因序列相似度分析#

题目链接

基因序列相似度分析

题目描述

给定一个待测基因片段和一组基因序列数据库，需要找出与待测片段最相似的序列。相似度通过“突变距离”（莱文斯坦距离）来衡量，即一个序列转换为另一个所需的最少单碱基操作（替换、插入、删除）次数。

输入:

第一行是一个整数 $M$ ，代表可接受的最大突变容忍度。
第二行是一个整数 $N$ ，代表基因数据库中序列的总数。
接下来 $N$ 行，每行是一个已知的基因序列。
最后一行是待测的基因片段。

输出:

精确匹配：如果存在与待测片段完全相同的序列，直接输出该序列。
模糊匹配：如果没有精确匹配，则输出所有突变距离小于等于 $M$ 的序列。结果需先按突变距离从小到大排序，距离相同时按字典序排序，用空格隔开。
无匹配：如果上述两种情况都不满足，则输出 None。

解题思路

本题的核心是计算两个字符串之间的莱文斯坦距离，并根据距离进行分类输出。莱文斯坦距离是动态规划的经典应用。

1. 莱文斯坦距离计算 我们可以定义一个二维 DP 数组 $dp[i][j]$ ，表示第一个字符串的前 $i$ 个字符 $s_1[0 \dots i-1]$ 与第二个字符串的前 $j$ 个字符 $s_2[0 \dots j-1]$ 之间的莱文斯坦距离。

状态定义: $dp[i][j]$ 是 $s_1$ 的前 $i$ 个字符和 $s_2$ 的前 $j$ 个字符之间的最小突变距离。
基本情况:
- $dp[i][0] = i$ ：将长度为 $i$ 的字符串转换为空字符串需要 $i$ 次删除操作。
- $dp[0][j] = j$ ：将空字符串转换为长度为 $j$ 的字符串需要 $j$ 次插入操作。
状态转移方程: 对于 $dp[i][j]$ ，我们考虑 $s_1[i-1]$ 和 $s_2[j-1]$ ：
- 如果 $s_1[i-1] == s_2[j-1]$ ，那么这两个字符匹配，不需要额外操作，距离继承自前一个状态： $dp[i][j] = dp[i-1][j-1]$
- 如果 $s_1[i-1] != s_2[j-1]$ ，我们需要进行一次操作。操作有三种可能：
  1. 替换: 将 $s_1[i-1]$ 替换为 $s_2[j-1]$ 。操作数 = $1 + dp[i-1][j-1]$
  2. 删除: 删除 $s_1[i-1]$ 。操作数 = $1 + dp[i-1][j]$
  3. 插入: 在 $s_1$ 后插入 $s_2[j-1]$ 。操作数 = $1 + dp[i][j-1]$ 我们取这三种操作中成本最小的一个： $dp[i][j] = 1 + \min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])$

最终， $s_1$ 和 $s_2$ 的莱文斯坦距离就是 $dp[\text{len}(s_1)][\text{len}(s_2)]$ 。

2. 整体逻辑

读取输入 $M$ , $N$ , 数据库序列和待测序列 $target$ 。
遍历数据库中的每个序列 $s$ ：
- 首先检查是否存在 $s == target$ 的精确匹配。如果找到，立即停止遍历，直接输出 $target$ 并结束程序。
如果遍历完整个数据库都没有找到精确匹配，则进入模糊匹配逻辑。
创建一个列表 $fuzzy\_matches$ 用于存储满足条件的序列和它们的距离。
再次遍历数据库中的每个序列 $s$ ：
- 计算 $s$ 和 $target$ 之间的莱文斯坦距离 $dist$ 。
- 如果 $dist \le M$ ，则将 ( $dist$ , $s$ ) 这个组合存入 $fuzzy\_matches$ 。
遍历结束后，检查 $fuzzy\_matches$ 列表：
- 如果列表为空，说明没有找到任何模糊匹配，输出 None。
- 如果列表不为空，对其进行排序。排序规则为：首先按距离 $dist$ 升序，如果距离相同，则按序列 $s$ 的字典序升序。
- 将排序后的序列用空格连接并输出。

代码

cpp
java
python

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

using namespace std;

// 计算莱文斯坦距离
int levenshtein_distance(const string& s1, const string& s2) {
    int m = s1.length();
    int n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

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

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
            dp[i][j] = min({dp[i - 1][j] + 1,        // 删除
                            dp[i][j - 1] + 1,        // 插入
                            dp[i - 1][j - 1] + cost}); // 替换
        }
    }
    return dp[m][n];
}

struct Match {
    string seq;
    int dist;
};

bool compareMatches(const Match& a, const Match& b) {
    if (a.dist != b.dist) {
        return a.dist < b.dist;
    }
    return a.seq < b.seq;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m, n;
    cin >> m >> n;
    vector<string> db(n);
    for (int i = 0; i < n; ++i) {
        cin >> db[i];
    }
    string target;
    cin >> target;

    // 检查精确匹配
    for (const auto& seq : db) {
        if (seq == target) {
            cout << target << "\n";
            return 0;
        }
    }

    // 模糊匹配
    vector<Match> fuzzy_matches;
    for (const auto& seq : db) {
        int dist = levenshtein_distance(seq, target);
        if (dist <= m) {
            fuzzy_matches.push_back({seq, dist});
        }
    }

    if (fuzzy_matches.empty()) {
        cout << "None\n";
    } else {
        sort(fuzzy_matches.begin(), fuzzy_matches.end(), compareMatches);
        for (size_t i = 0; i < fuzzy_matches.size(); ++i) {
            cout << fuzzy_matches[i].seq << (i == fuzzy_matches.size() - 1 ? "" : " ");
        }
        cout << "\n";
    }

    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

class Match implements Comparable<Match> {
    String seq;
    int dist;

    public Match(String seq, int dist) {
        this.seq = seq;
        this.dist = dist;
    }

    @Override
    public int compareTo(Match other) {
        if (this.dist != other.dist) {
            return Integer.compare(this.dist, other.dist);
        }
        return this.seq.compareTo(other.seq);
    }
}

public class Main {
    // 计算莱文斯坦距离
    private static int levenshteinDistance(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
                dp[i][j] = Math.min(dp[i - 1][j - 1] + cost, // 替换
                                   Math.min(dp[i - 1][j] + 1,  // 删除
                                            dp[i][j - 1] + 1)); // 插入
            }
        }
        return dp[m][n];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine(); // consume newline
        
        List<String> db = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            db.add(sc.nextLine());
        }
        String target = sc.nextLine();

        // 检查精确匹配
        for (String seq : db) {
            if (seq.equals(target)) {
                System.out.println(target);
                return;
            }
        }

        // 模糊匹配
        List<Match> fuzzyMatches = new ArrayList<>();
        for (String seq : db) {
            int dist = levenshteinDistance(seq, target);
            if (dist <= m) {
                fuzzyMatches.add(new Match(seq, dist));
            }
        }

        if (fuzzyMatches.isEmpty()) {
            System.out.println("None");
        } else {
            Collections.sort(fuzzyMatches);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < fuzzyMatches.size(); i++) {
                sb.append(fuzzyMatches.get(i).seq);
                if (i < fuzzyMatches.size() - 1) {
                    sb.append(" ");
                }
            }
            System.out.println(sb.toString());
        }
    }
}

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    # 初始化DP表
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            cost = 0 if s1[i - 1] == s2[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1,        # 删除
                           dp[i][j - 1] + 1,        # 插入
                           dp[i - 1][j - 1] + cost) # 替换
    return dp[m][n]

# 读取输入
m = int(input())
n = int(input())
db = [input() for _ in range(n)]
target = input()

# 检查精确匹配
exact_match_found = False
for seq in db:
    if seq == target:
        print(target)
        exact_match_found = True
        break

if not exact_match_found:
    # 模糊匹配
    fuzzy_matches = []
    for seq in db:
        dist = levenshtein_distance(seq, target)
        if dist <= m:
            fuzzy_matches.append((dist, seq))
    
    if not fuzzy_matches:
        print("None")
    else:
        # 排序：先按距离，再按字典序
        fuzzy_matches.sort()
        # 提取排序后的序列
        result = [seq for dist, seq in fuzzy_matches]
        print(" ".join(result))

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(N \cdot L_{db} \cdot L_{target})$ ，其中 $N$ 是数据库中序列的数量， $L_{db}$ 是数据库中序列的最大长度， $L_{target}$ 是待测序列的长度。我们需要对 $N$ 个序列中的每一个都计算一次莱文斯坦距离，而单次计算的复杂度是两个字符串长度的乘积。
空间复杂度： $\mathcal{O}(L_{db} \cdot L_{target})$ ，主要开销来自于计算莱文斯坦距离时使用的二维 $dp$ 表。