博客打卡-人类基因序列功能问题动态规划

题目如下：

众所周知，人类基因可以被认为是由4个核苷酸组成的序列，它们简单的由四个字母A、C、G和T表示。生物学家一直对识别人类基因和确定其功能感兴趣，因为这些可以用于诊断人类疾病和设计新药物。

生物学家确定新基因序列功能的方法之一是，用新基因作为查询搜索数据库，要搜索的数据库中存储了基因序列及其功能。数据库搜索将返回数据库中与查询基因相似的基因序列表。

生物学家认为序列相似性往往意味着功能相似性，因此新基因的功能可能是来自列表的基因的功能之一，要确定哪一个是正确的，需要另一系列的生物实验。请设计一个动态规划算法比较两个基因并确定它们的相似性，然后编写程序实现该算法。

给定两个基因AGTGATG和GTTAG，它们有多相似？测量两个基因相似性的一种方法称为对齐。在对齐中，如果需要，将空间插入基因的适当位置以使它们等长，并根据评分矩阵评分所得基因。

例如，在AGTGATG中插入一个空格得到AGTGAT-G，并且在GTTAG中插入3个空格得到-GT—TAG。空格用减号(-)表示。两个基因现在的长度相等，这两个字符串对齐如下：

AGTGAT-G

-GT--TAG

在这种对齐中有4个字符是匹配的，即第2个位置的G，第3个位置的T，第6个位置的T和第8个位置的G。每对对齐的字符根据评分矩阵分配一个分数，不允许空格之间进行匹配。上述对齐的得分为(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。评分矩阵如下：

当然，还有许多其他的对齐方式（将不同数量的空格插入到不同的位置得到不同的对齐方式），例如：

AGTGATG

-GT TA -G

该对齐的得分数是(-3)+5+5+(-2)+5+(-1)=14，这个对齐更好，且是最佳的。因此，这两个基因的相似性是14。

输入格式:

输入由T个测试用例组成，T在第1行输入，每个测试用例由两行组成，每行包含一个整数（表示基因的长度）和一个基因序列，每个基因序列的长度至少为1，不超过100。

输出格式:

打印每个测试用例的相似度，每行一个相似度。

输入样例:

在这里给出一组输入。例如：

2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA

输出样例:

在这里给出相应的输出。例如：

14
21

解题思路如下：

题目要求计算两个基因序列的相似性得分，我们可以通过动态规划方法找到最优的对齐方式。设dp[i][j] 表示序列 gene1[0..i-1] 和 gene2[0..j-1] 的最优对齐得分。设评分矩阵similarityMatrix的行和列分别对应 A, C, G, T, -。利用评分矩阵进行匹配，对比三种情况：gene1[i-1] 和 gene2[j-1] 直接匹配，gene1[i-1] 与空格匹配，gene2[j-1] 与空格匹配，取这三种情况的最大值作为 dp[i][j] 。

具体代码如下：

import java.util.Scanner;public class Main {private static final int MAX_N = 100;private static final int[][] similarityMatrix = {{ 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 }};private static int iGene(char a) {switch (a) {case 'A': return 0;case 'C': return 1;case 'G': return 2;case 'T': return 3;default: return 4; // Gap character '-'}}private static int calculateSimilarity(String gene1, String gene2, int n1, int n2) {int[][] dp = new int[n1 + 1][n2 + 1];for (int i = 1; i <= n1; i++) {dp[i][0] = dp[i - 1][0] + similarityMatrix[iGene(gene1.charAt(i - 1))][4];}for (int j = 1; j <= n2; j++) {dp[0][j] = dp[0][j - 1] + similarityMatrix[iGene(gene2.charAt(j - 1))][4];}for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {int match = dp[i - 1][j - 1] + similarityMatrix[iGene(gene1.charAt(i - 1))][iGene(gene2.charAt(j - 1))];int delete = dp[i - 1][j] + similarityMatrix[iGene(gene1.charAt(i - 1))][4];int insert = dp[i][j - 1] + similarityMatrix[iGene(gene2.charAt(j - 1))][4];dp[i][j] = Math.max(Math.max(match, delete), insert);}}return dp[n1][n2];}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int T = scanner.nextInt();while (T-- > 0) {int n1 = scanner.nextInt();String gene1 = scanner.next();int n2 = scanner.nextInt();String gene2 = scanner.next();int similarity = calculateSimilarity(gene1, gene2, n1, n2);System.out.println(similarity);}scanner.close();}
}

运行结果如下：