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

1、DNA是遺傳信息的載體,遺傳信息的作用通常由蛋白質(zhì)的功能來表現(xiàn),但DNA并非蛋白質(zhì)合成的直接模板,合成蛋白質(zhì)的模板是RNA。RNA二級結(jié)構(gòu)預(yù)測問題是計算機(jī)科學(xué)和生物信息學(xué)的基本課題之一,RNA二級結(jié)構(gòu)預(yù)測用于蛋白質(zhì)功能分析,序列對比分析法及熱動力學(xué)最小自由能量方法是RNA二級結(jié)構(gòu)預(yù)測的兩種基本方法,序列對比分析法的基本思想,是找出檢測序列和目標(biāo)序列的相似性。序列對比的最終實(shí)現(xiàn),必須依賴于某個數(shù)學(xué)模型,在序列非常相近或新的獨(dú)立序列的情況下

2、,序列對比法不適應(yīng)。目前熱動力學(xué)最小自由能量方法已成為RNA二級結(jié)構(gòu)預(yù)測的最常用方法。 目前預(yù)測RNA二級結(jié)構(gòu)的大多數(shù)算法僅預(yù)測嵌套的RNA二級結(jié)構(gòu),不允許偽結(jié)點(diǎn)存在。但偽結(jié)點(diǎn)在幾種已知RNA中具有重要功能。如Pleij等人于1985年預(yù)測了RnaSe P RNAS中的偽結(jié)點(diǎn)結(jié)構(gòu),并由Kock等人于1998年予以證實(shí)。 包含偽結(jié)點(diǎn)的RNA二級結(jié)構(gòu)預(yù)測問題是NPC問題。目前預(yù)測包含偽結(jié)點(diǎn)的RNA二級結(jié)構(gòu)的動態(tài)規(guī)劃算法有：Rivals算法、

3、B.Lyngsφ算法和Jens Reeder的代數(shù)動態(tài)規(guī)劃等算法。Rivals算法、B.Lyngsφ算法都可預(yù)測包含偽結(jié)點(diǎn)的RNA二級結(jié)構(gòu).Rivas算法可計算包含任意平面?zhèn)谓Y(jié)點(diǎn)和特定條件下的非平面?zhèn)谓Y(jié)點(diǎn)結(jié)構(gòu),其時間復(fù)雜度為O(n~6),空間復(fù)雜度為O(n~4)。Lyngsφ算法僅可計算包含一個平面?zhèn)谓Y(jié)點(diǎn)的結(jié)構(gòu),其時間復(fù)雜度為O(n~5),空間復(fù)雜度為O(n~3)。最近較好的預(yù)測算法使用其O(n~4)時間和O(n~3)的空間預(yù)測任意的平