含假結RNA二級結構圖的語法及拓撲分類.pdf

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

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

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

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

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