1080 Human Gene Functions

1080 Human Gene Functions


２つの遺伝子がどれだけ似ているか(similarity)を計算する。
これまたPKUに興味を持つきっかけになった1159 Palindrome（halwhiteがLCSを教えてくれて解けた）に似ているなぁと思ってDPの練習としてやってみた。

dp[i][j]をseq1のi文字目、seq2のj文字目までのsimilarityの最大値とする。

• dp[0][0]は0
• dp[0][i2] (1≦i2≦len2)はseq2に全てワイルドカード'-'をぶつけた場合だから、徐々にsimilarityは下がっていく。
• dp[i1][0] (1≦i1≦len1)はseq1に全てワイルドカード'-'をぶつけた場合だから、徐々にsimilarityは下がっていく。
• dp[i1][i2] (1≦i1≦len1, 1≦i2≦len2)は場合分け。

seq1 ○○○☆
seq2 ××☆

dp[i1][i2] = dp[i1-1][i2-1] + calcScore(seq1[i1-1], seq2[i2-1]); // (=5)

seq1 ○○○□
seq2 ××△

dp[i1][i2] = max(dp[i1-1][i2-1] + calcScore(seq1[i1-1], seq2[i2-1]), // □と△を対応させた場合
                 dp[i1-1][i2] + calcScore('-', seq1[i1-1]), // □にワイルドカードを対応させた場合
                 dp[i1][i2-1] + calcScore('-', seq2[i2-1])) // △にワイルドカードを対応させた場合

LCSの応用形だった。

#include<cstdio>
#include<algorithm>

using namespace std;

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 calcScore(char c1, char c2) {
    int i1, i2;
    switch (c1) {
    case 'A':
	i1 = 0;
	break;
    case 'C':
	i1 = 1;
	break;
    case 'G':
	i1 = 2;
	break;
    case 'T':
	i1 = 3;
	break;
    case '-':
	i1 = 4;
	break;
    }
    switch (c2) {
    case 'A':
	i2 = 0;
	break;
    case 'C':
	i2 = 1;
	break;
    case 'G':
	i2 = 2;
	break;
    case 'T':
	i2 = 3;
	break;
    case '-':
	i2 = 4;
	break;
    }
    return score[i1][i2];
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
	int len1, len2;
	char seq1[101], seq2[101];
	scanf("%d %s %d %s", &len1, seq1, &len2, seq2);
	int dp[len1+1][len2+1];
	dp[0][0] = 0;
	for (int i2 = 1; i2 <= len2; ++i2) {
	    dp[0][i2] = dp[0][i2-1] + calcScore('-', seq2[i2-1]);
	}
	for (int i1 = 1; i1 <= len1; ++i1) {
	    dp[i1][0] = dp[i1-1][0] + calcScore('-', seq1[i1-1]);
	}

	for (int i1 = 1; i1 <= len1; ++i1) {
	    for (int i2 = 1; i2 <= len2; ++i2) {
		if (seq1[i1-1] == seq2[i2-1]) {
		    dp[i1][i2] = dp[i1-1][i2-1] + calcScore(seq1[i1-1], seq2[i2-1]);
		}
		else {
		    dp[i1][i2] = max(dp[i1-1][i2-1] + calcScore(seq1[i1-1], seq2[i2-1]),
				     max(dp[i1-1][i2] + calcScore('-', seq1[i1-1]),
					 dp[i1][i2-1] + calcScore('-', seq2[i2-1])));
					 
		}
	    }
	}
	printf("%d\n", dp[len1][len2]);
    }
}

calcScoreのところをうまく書けないかなぁ…
MAPとか？