动态规划算法预测rna的二级结构备忘录

动态规划算法是RNA二级结构预测中的一种常见方法，下面是一个预测RNA二级结构的动态规划算法的备忘录：

1. 定义状态：用一个二维数组dp[i][j]表示RNA序列中从位置i到位置j的最大配对数。

2. 状态转移方程：dp[i][j]可以由下列三种情况中的最大值得到：
a. 如果i和j配对，那么dp[i][j] = dp[i+1][j-1] + 1；
b. 如果i和j不配对，那么可以将i和k配对，其中i<k<j，那么dp[i][j] = max(dp[i][k] + dp[k+1][j])；
c. 如果i和j不配对，那么可以将j和k配对，其中i<k<j，那么dp[i][j] = max(dp[i][k] + dp[k+1][j])。

3. 初始化：对角线上的dp[i][i]均为0。

4. 计算顺序：按照i从大到小，j从小到大的顺序计算dp[i][j]。

5. 输出结果：找到使得dp[1][n]最大的k，然后根据k将RNA序列分成左右两部分，分别递归求解左右两部分的最大配对数。

需要注意的是，以上算法只能得到RNA的最稳定二级结构，而RNA的二级结构可能有多个。因此，需要结合其他算法和实验数据来综合预测RNA的二级结构。