RNA二級結(jié)構(gòu)預測的快速計算.pdf

1、RNA二級結(jié)構(gòu)預測要求根據(jù)RNA序列計算序列中符號的配對集，使得配對集所形成的結(jié)構(gòu)具有最小自由能量。如何得到更加準確的預測結(jié)構(gòu)，是近三十年來生物信息學的熱點之一。 以往人們采用序列比對分析法獲得RNA序列的準確二級結(jié)構(gòu)，但是該方法人工工作量大，條件限制較多，因此無法廣泛應(yīng)用。目前熱動力學最小自由能量方法已成為：RNA二級結(jié)構(gòu)預測的最常用方法。基于動態(tài)規(guī)劃和最鄰近能量模型的Mfold算法是計算RNA二級結(jié)構(gòu)最小自由能量的經(jīng)典方法。

2、 假結(jié)是RNA中普遍存在的二級結(jié)構(gòu)單元。但Mfold算法不能預測假結(jié)。目前預測假結(jié)的最好算法是Rivas算法。該算法能得到最優(yōu)平面假結(jié)結(jié)構(gòu)和部分非平面假結(jié)結(jié)構(gòu)，但算法的時間復雜度太高。 本文首先實現(xiàn)和改進Mfold算法?；诃h(huán)和最臨近能量模型，使用實驗室測量的能量數(shù)據(jù)，通過動態(tài)規(guī)劃計算子鏈的最小自由能量，并且計算最優(yōu)二級結(jié)構(gòu)，實現(xiàn)Mfold算法。把同軸堆疊模型加入Mfold算法，從而得到具有更低的自由能量的RNA二級結(jié)構(gòu)

3、，實現(xiàn)Mfold算法的改進。改進算法的時間和空間復雜度與Mfold算法相同。 我們通過實驗比較了Mfold算法和改進算法，結(jié)果表明，相比Mfold算法，改進算法的預測準確度由76.43％提高到78.25％。 然后本文實現(xiàn)了多折疊的次優(yōu)算法。該算法首先把線性RNA序列抽象為環(huán)鏈，任意選擇一個基對將環(huán)鏈劃分成內(nèi)段和外段，分別計算內(nèi)段和外段的能量和結(jié)構(gòu)。內(nèi)段和外段的能量之和為次優(yōu)能量，結(jié)構(gòu)之組合為次優(yōu)結(jié)構(gòu)，其時間復雜度是O(n

4、<'3>)，空間復雜度是O(n<'2>)。次優(yōu)算法為RNA二級結(jié)構(gòu)分析提供更多有用的信息。 隨后本文給出了一個計算簡單假結(jié)的二級結(jié)構(gòu)算法。通過任意選擇兩個交叉的基對，把序列劃分為五段，分別計算每一段的能量和結(jié)構(gòu)，從而得到包含一個簡單假結(jié)的二級結(jié)構(gòu)。該算法的時間和空間復雜度與Mfold算法相同。 最后，本文給出30余個實際序列的實驗測試，進行對比分析和準確度計算。 本文的主要創(chuàng)新點為： 1.引入同軸堆疊改進