㈠ python动态规划算法预测RNA折叠（RNAfold)
RNA分子通过特定方式折叠形成结构，这与蛋白质分子类似。碱基对构成结构的基本单元，RNA分子内部形成碱基对。RNA结构可能包括以下碱基对：A-U、G-C、A-C、G-U。预测RNA二级结构的简化算法之一是Nussinov算法，本文将用Python实现此算法。
Nussinov算法是一种动态规划算法，通过递归计算最大碱基对数。算法使用一个矩阵来存储从子序列到子序列能形成的最大碱对数。动态规划矩阵D初始化为D[i][i]=0且所有位置均在RNA序列中。矩阵大小等于RNA序列长度的两倍。例如，RNA序列"AUG"对应D矩阵如下：
为了填充矩阵，需使用递归方法。在递归步骤中，未配对的核苷酸位于结构的两侧。如果位置i和j配对，则将上一个得分加到矩阵[D[i][j]]=max[D[i][j], D[i][j-1]+1, D[i-1][j]].不配对时[D[i][j]]=max[D[i][j], D[i][j-1], D[i-1][j]].回溯算法用于确定实际结构，从右上角开始回溯以找到获得最高碱基对数的步骤。
Python实现中，设计了RNAfold类来包装整个函数。创建了一个解析读取fasta文件的python类来读取序列。对功能进行了验证，使用较长序列进行检查，结果显示矩阵结果和折叠结构正确。
参考文献：Nussinov, R; Jacobson, A B (1980). "Fast algorithm for predicting the secondary structure of single-stranded RNA". Proceedings of the National Academy of Sciences of the United States of America.