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

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

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

3、，實(shí)現(xiàn)Mfold算法的改進(jìn)。改進(jìn)算法的時間和空間復(fù)雜度與Mfold算法相同。 我們通過實(shí)驗(yàn)比較了Mfold算法和改進(jìn)算法，結(jié)果表明，相比Mfold算法，改進(jìn)算法的預(yù)測準(zhǔn)確度由76.43％提高到78.25％。 然后本文實(shí)現(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)，其時間復(fù)雜度是O(n

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