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

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

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

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