算法-动态规划-RNA最小自由能问题C语言求解

Question

RNA分子的一级结构可以看作是由核苷酸顺序排列构成的一条链，由于含有碱基不同，这些核苷酸分别标记为字母A，C，G，U。给定RNA一级结构，按照以下原则求具有最小自由能的RNA二级结构。

1. 配对只在U与A，C与G之间进行。
2. 在发夹环部位不允许出现“尖角”，至少含有3个不参与匹配的核苷酸；换句话说，如果位置i与j配对，那么i≤j-4。
3. 不允许重复配对，每个核苷酸只能参加一个配对。

不允许交叉配对，即如果4个碱基位置i1，i2，j1，j2满足i1<i2<j1<j2 ，那么不允许i1-j1，i2-j2 配对，但可以i1-j2，i2-j1允许配对。

Answer 1

#include <stdio.h>
#include <string.h>

// 计算RNA二级结构的最小自由能
int minimumFreeEnergy(char rna[], int n) {
    int dp[n][n];  // 动态规划数组

    memset(dp, 0, sizeof(dp));  // 初始化dp数组为0

    for (int len = 3; len < n; len++) {
        for (int i = 0; i < n - len; i++) {
            int j = i + len;
            if ((rna[i] == 'A' && rna[j] == 'U') || (rna[i] == 'U' && rna[j] == 'A') ||
                (rna[i] == 'C' && rna[j] == 'G') || (rna[i] == 'G' && rna[j] == 'C')) {
                dp[i][j] = dp[i + 1][j - 1] + 1;
            }

            for (int k = i; k < j; k++) {
                if (dp[i][j] < dp[i][k] + dp[k + 1][j]) {
                    dp[i][j] = dp[i][k] + dp[k + 1][j];
                }
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    char rna[] = "ACGUAUCG";
    int n = strlen(rna);

    int minFreeEnergy = minimumFreeEnergy(rna, n);
    printf("Minimum Free Energy: %d\n", minFreeEnergy);

    return 0;
}