包含假結(jié)的RNA結(jié)構(gòu)預(yù)測算法研究

1、包含假結(jié)的RNA結(jié)構(gòu)預(yù)測算法研究RNA（核糖核酸）作為生物大分子具有十分重要的生物學(xué)功能,RNA結(jié)構(gòu)預(yù)測 是計(jì)算分子生物學(xué)的基本課題之一,也是當(dāng)今國際研究熱點(diǎn)。RNA結(jié)構(gòu)預(yù)測中很 多問題都是NP-難的,與其設(shè)計(jì)不出精確算法,不如去設(shè)計(jì)其多項(xiàng)式時(shí)間近似算 法,去指導(dǎo)該類問題的生物應(yīng)用。RNA三級結(jié)構(gòu)是比較穩(wěn)定的結(jié)構(gòu),而預(yù)測RXA三級結(jié)構(gòu)需先預(yù)測RNA二級結(jié) 構(gòu)。預(yù)測RNA二級結(jié)構(gòu)方法主要有序列對比分析法和最小自由能量法,序列對比 分析方法預(yù)測RNA二級結(jié)構(gòu),是通過在不同生物有機(jī)體中起相同生物功能的一級 結(jié)構(gòu)進(jìn)行比對得到RNA堿基序列的二級結(jié)構(gòu)。許多生物有機(jī)體RNA分子的同源序列不易得到,需要耗費(fèi)

2、大量人力，因而序 列對比分析方法的預(yù)測效率較低,利用最小能量方法來預(yù)測RNA二級結(jié)構(gòu)是廣泛 采用方法之一 Zuker提出的Mfold算法是早期基于最小能量方法來研究的二級結(jié) 構(gòu)預(yù)測算法,最小能量方法的本質(zhì)是基于熱動力學(xué)模型尋找RNA堿基序列所能形 成的各種結(jié)構(gòu)中具有最小能量的結(jié)構(gòu)。Mfold算法的預(yù)測正確率為70%左右，但該 算法不能預(yù)測假結(jié)和更復(fù)雜的結(jié)構(gòu)，因而其應(yīng)用受到較大限制。假結(jié)是RNA分子中最廣泛的三級結(jié)構(gòu)單元是較復(fù)雜但穩(wěn)定的RNA結(jié)構(gòu)。假 結(jié)在不同的RNA分子中具有構(gòu)造、干擾、催化、調(diào)節(jié)等重要功能,包含假結(jié)的RNA 預(yù)測是當(dāng)今國際RNA結(jié)構(gòu)預(yù)測研究的關(guān)鍵點(diǎn)和研究熱點(diǎn),預(yù)測包含任意假結(jié)

3、的 RNA二級結(jié)構(gòu)問題是NP難的,至今未找到該問題有效的多項(xiàng)式算法,近似算法則 為求解NP難問題的核心方法。連續(xù)基對構(gòu)成堆置,基對的交叉形成假結(jié)點(diǎn),莖區(qū)的交叉構(gòu)成假結(jié)結(jié)構(gòu)，目前 現(xiàn)有的預(yù)測含假結(jié)的RNA二級結(jié)構(gòu)的算法,對較大的RNA分子計(jì)算很困難?；?莖區(qū)組合來尋找RNA優(yōu)化結(jié)構(gòu)成為包含假結(jié)RNA結(jié)構(gòu)預(yù)測重要方法,Benedeti等 人提出基于莖區(qū)組合的能量集合算法來預(yù)測RNA二級結(jié)構(gòu),Ruan等人提出基于莖 區(qū)的啟發(fā)式算法來預(yù)測包含假結(jié)的RNA二級結(jié)構(gòu),其時(shí)間復(fù)雜度為0)出4),空間 復(fù)雜度為0(n2)。本文根據(jù)RNA假結(jié)表示模型,基于RNA莖區(qū)結(jié)構(gòu)相對穩(wěn)定的特征和最小自由 能量原理,提出

4、了預(yù)測含假結(jié)的RNA二級結(jié)構(gòu)的啟發(fā)式算法,時(shí)間復(fù)雜度為0(n3) 和空間復(fù)雜度為0(n2),通過在RNA假結(jié)庫實(shí)驗(yàn)表明，該算法有較好的預(yù)測特異性 和敏感性。連續(xù)堆疊可構(gòu)成莖區(qū),針對基于莖區(qū)的RNA優(yōu)化結(jié)構(gòu),將序列劃分為長 度不大于t(t>2)的子序列，計(jì)算由長度不大于t的子序列構(gòu)成的最優(yōu)結(jié)構(gòu)作 為整個(gè)序列的近似結(jié)構(gòu),設(shè)計(jì)出預(yù)測任意假結(jié)的1+ ( >0)多項(xiàng)式時(shí)間近似 方案(PTAS)。通過對假結(jié)加以限制來預(yù)測簡單假結(jié)的最小能量算法是目前較多的含假結(jié) 二級結(jié)構(gòu)預(yù)測方法,Rivas和Eddy提出的Rivas算法使用預(yù)測任意的平面假結(jié)和 部分非平面假結(jié),其時(shí)間復(fù)雜度為0S6)和空間復(fù)雜度

5、為0(n4) o Jens和Robert 提出的JR算法可預(yù)測簡單的嵌套假結(jié)，時(shí)間復(fù)雜度為0(n4)時(shí)間，空間復(fù)雜度為 0(n2)空間,Lyngs (?)和Pedersen使用相容結(jié)構(gòu)代替Rivas算法中的缺口矩陣, 提出了 Lyngso算法，算法時(shí)間復(fù)雜度為0(n5)和空間復(fù)雜度為0(n3),但該算法僅 能預(yù)測一個(gè)平面假結(jié)。連續(xù)堆，疊形成莖區(qū),堆疊和莖區(qū)是穩(wěn)定RNA結(jié)構(gòu)的主要作用,Cary和Storm 提出的最大權(quán)匹配算法可以折疊RNA假結(jié)結(jié)構(gòu)，但以預(yù)測正確率降低為代價(jià)。堆 疊最大化問題也是近年來人們十分關(guān)注的含假結(jié)RNA二級結(jié)構(gòu)預(yù)測問題。在平面RNA二級結(jié)構(gòu)中，允許假結(jié)的存在使計(jì)算最大堆疊

6、數(shù)問題成為NP難 的,leong. S等人提出了最大堆疊基對數(shù)問題，設(shè)計(jì)了帶任意假結(jié)的RNA二級結(jié)構(gòu) 預(yù)測近似算法，分別設(shè)計(jì)出平面二級結(jié)構(gòu)的近似算法和普通二級結(jié)構(gòu)的近似算法, 并且證明了平面RNA二級結(jié)構(gòu)中求含假結(jié)的最大堆疊數(shù)問題也是NP難的。分析 了包含假結(jié)的RNA二級結(jié)構(gòu),剖析連續(xù)堆登對和假結(jié)的結(jié)構(gòu)特性,分析求解最大 堆疊數(shù)的近似算法,其近似性能比為1/3,給出了證明，討論了最大堆疊數(shù)問題的 計(jì)算復(fù)雜性,并且可以預(yù)測更復(fù)雜的假結(jié)。給出RNA堿基序列S和正整數(shù)h,通過把三劃分匹配這一 NP難問題規(guī)約到該 問題，判斷在平面RA二級結(jié)構(gòu)中是否可能存在大于等于h的最大堆疊數(shù),從而證 明了在平面RN

7、A二級結(jié)構(gòu)中含假結(jié)的最大堆疊數(shù)問題也是NP難的。本文的主要 工作為：1、基于最小H由能量的RNA結(jié)構(gòu)的表示建模是RNA結(jié)構(gòu)預(yù)測的關(guān)鍵。對于假結(jié)而言,可分為平面假結(jié)和非平面假結(jié),假結(jié)可形成嵌套或并列結(jié)構(gòu)， 由兩個(gè)莖區(qū)結(jié)構(gòu)可形成嵌套假結(jié)，由內(nèi)環(huán)和凸起可構(gòu)成平面假結(jié),平面假結(jié)經(jīng)常 出現(xiàn)在RNA分子中，交叉假結(jié)也存在于RNA中。莖區(qū)在RNA結(jié)構(gòu)穩(wěn)定性中承擔(dān)著 重要作用，基于莖區(qū)的交叉可形成假結(jié)的特性,可利用莖區(qū)結(jié)構(gòu)建立關(guān)于假結(jié)的 表示模型。在PseudoBase假結(jié)數(shù)據(jù)庫中，大部分為平面假結(jié)，也包含少量的非平面假結(jié)。 通過設(shè)計(jì)啟發(fā)函數(shù)、用恰當(dāng)?shù)募俳Y(jié)表示建模來預(yù)測RNA假結(jié)結(jié)構(gòu)可取得較好的效 果。根據(jù)R

8、NA假結(jié)表示模型，基于最小自由能量原理，設(shè)計(jì)了預(yù)測任意平面假結(jié) 和非平面假結(jié)的啟發(fā)式算法,通過在PseudoBase等假結(jié)數(shù)據(jù)庫實(shí)驗(yàn)驗(yàn)證表明，算 法的預(yù)測敏感性特異性和預(yù)測準(zhǔn)確度均有所提高,其時(shí)間復(fù)雜度為0S3),空間 復(fù)雜度為0(n2)。2、一般來說，連續(xù)的堆疊可形成莖區(qū)結(jié)構(gòu)，莖區(qū)結(jié)構(gòu)可使RNA 結(jié)構(gòu)能量降低，結(jié)構(gòu)更穩(wěn)定。通過莖區(qū)的組合優(yōu)化特性來預(yù)測RNA優(yōu)化結(jié)構(gòu)是我們采用的重要方法,莖區(qū) 之間可形成并列結(jié)構(gòu)、嵌套結(jié)構(gòu)和交叉結(jié)構(gòu)。含有交叉結(jié)構(gòu)即包含假結(jié),假結(jié)的 存在是RNA結(jié)構(gòu)預(yù)測變得復(fù)雜,是問題難解性的重要因素,使得設(shè)計(jì)多項(xiàng)式時(shí)間 算法變得異常困難，設(shè)計(jì)該問題的近似算法或近似方案成為處理該

9、問題的重要手 段。針對基于莖區(qū)的RNA優(yōu)化結(jié)構(gòu)，把RNA堿基序列用短莖進(jìn)行劃分，計(jì)算由長度 不大于t的莖區(qū)構(gòu)成的結(jié)構(gòu)作為整個(gè)序列的近似結(jié)構(gòu),重新分析了預(yù)測任意假結(jié) 的1+（>O）多項(xiàng)式時(shí)間近似方案。3、在RNA堿基序列中，連續(xù)的兩個(gè)堿基 對可構(gòu)成堆疊,從堆疊的角度看，多個(gè)連續(xù)堿基對可形成連續(xù)堆疊,連續(xù)堆疊中堆 疊的個(gè)數(shù)越多，則RNA結(jié)構(gòu)越穩(wěn)定。在RNA結(jié)構(gòu)預(yù)測中,包含假結(jié)的計(jì)算最大堆疊數(shù)問題也是NP難的，針對該類 問題,與其設(shè)計(jì)不出多項(xiàng)式時(shí)間精確算法,不如退而求其次,通過其內(nèi)在特性的深 入分析,設(shè)計(jì)求解該類問題的多項(xiàng)式時(shí)間近似算法。分析其近似性能比,嘗試降低 近似比，指導(dǎo)該問題的求解。針對連續(xù)堆疊對的結(jié)構(gòu)特性,重新分析了 RNA二級結(jié)構(gòu)最大堆疊數(shù)問題,通 過在RNA折梯結(jié)構(gòu)中查找連續(xù)堆疊,并對內(nèi)在特性加以剖析，分析了計(jì)算最大堆 疊數(shù)的近似算法,其近似性能比為3,并給出了近似性能比的證明。本文下一步的 主