含假結(jié)RNA二級結(jié)構(gòu)圖的語法及拓?fù)浞诸?pdf

1、RNA的生物學(xué)功能很大程度上決定子其三維空間結(jié)構(gòu)?？臻g結(jié)構(gòu)一般通過x射線晶體衍射和核磁共振等實(shí)驗(yàn)方法獲得，但是實(shí)驗(yàn)方法技術(shù)難度高、耗資大且并非總是可行。因此理論預(yù)測：RNA空間結(jié)構(gòu)就非常必要，它可以提高認(rèn)識(shí)RNA空間結(jié)構(gòu)的效率，還可以指引實(shí)驗(yàn)研究的方向。 RNA二級結(jié)構(gòu)預(yù)測是其空間結(jié)構(gòu)預(yù)測的關(guān)鍵。目前，最小自由能法是預(yù)測RNA二級結(jié)構(gòu)最主要的方法，但二級結(jié)構(gòu)內(nèi)部假結(jié)的存在使得該方法是NP完全的，這類方法只能考慮具有一定結(jié)構(gòu)特征

2、的假結(jié)，從而將時(shí)間復(fù)雜度控制在多項(xiàng)式范圍內(nèi)。視結(jié)構(gòu)特征的不同，復(fù)雜度從D(n3)到D(n6)不等，復(fù)雜度越高能預(yù)測的目標(biāo)集也越廣，目前不存在速度快、目標(biāo)集廣的“好”方法。本文以時(shí)間復(fù)雜度為O(n6)的Rivas與Eddy算法的目標(biāo)集(R&E類)為全集，從文法和語言的角度提出了R&E類及其子類的弧圖語法，并從拓?fù)鋵W(xué)的角度將其分類，具體內(nèi)容包括： 1.提出了弧圖語法概念。RNA二級結(jié)構(gòu)弧圖是一種特殊的二級結(jié)構(gòu)圖，從最簡單的弧圖開始

3、，按照一定的替換規(guī)則對弧圖的小部件用較大的部件替換，從而得到一個(gè)弧圖類。那些體現(xiàn)結(jié)構(gòu)特征的最簡單的弧圖稱為初始弧圖，那些替換規(guī)則稱為重寫規(guī)則，初始弧圖和重寫規(guī)則兩類要素構(gòu)成弧圖語法。給定弧圖語法就決定著一個(gè)弧圖類，該類稱為弧圖語言?；D語法提供了一種把數(shù)量無限的弧圖映射成為數(shù)量有限的語法要素的研究方法，且具有易擴(kuò)展性。 2.給出了5個(gè)二級結(jié)構(gòu)算法類的弧圖語法。本文首先設(shè)計(jì)出.R&E類的弧圖語法，以R&E類弧圖語法的要素為全集，

4、給出其自小至大的子集PKF類、L&P類、D&P類、A&U類的弧圖語法，這幾個(gè)類閥具有真包含關(guān)系，這種關(guān)系直觀地從他們的弧圖語法要素中體現(xiàn)出來。通過研究這5個(gè)二級結(jié)構(gòu)類間的關(guān)系以及代表元素使全面掌握各類的內(nèi)容成為可能。 3.得到了平面R&E弧圖的語法判據(jù)。直觀地以平面圖的形式展示二級結(jié)構(gòu)有著很廣泛的需求，本文在他人研究的基礎(chǔ)上在更大范圍--R&E類內(nèi)給出基于弧圖語法的判別依據(jù)，同時(shí)給出了平面嵌入算法。通過可平面R&E類的弧圖語法

5、，在R&E類內(nèi)部完全解決了可平面弧圖的平面嵌入問題。在R&E類外部也進(jìn)行了初步的探索，得到一些有益的例證。 4.實(shí)現(xiàn)了R&E弧圖的書嵌入分類。RNA二級結(jié)構(gòu)圖的書嵌入自1999年提出以來由于其高時(shí)閾復(fù)雜性(NP完全)而一直停留在概念上。本文以R&E類的弧圖語法為基礎(chǔ)，以弧圖的交叉關(guān)系圖為橋梁，最終通過交叉關(guān)系圖的極大團(tuán)覆蓋求出任意R&E弧圖的書嵌入數(shù)并給出嵌入方案，將傳統(tǒng)意義上的NP完全問題在R&E類上用多項(xiàng)式時(shí)間加以解決。