㈠ 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.