資源描述：
《基于結(jié)構(gòu)信息的rna多序列比對(duì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、基于結(jié)構(gòu)信息的RNA多序列比對(duì)【摘要】本研究提出了一種考慮了結(jié)構(gòu)信息的同源RNA多序列比對(duì)算法，它先利用熱力學(xué)方法計(jì)算出每條序列的配對(duì)概率矩陣，得到結(jié)構(gòu)信息，由此構(gòu)造各條序列的結(jié)構(gòu)信息矢量，結(jié)合傳統(tǒng)序列比對(duì)方法，提出優(yōu)化目標(biāo)函數(shù)，采用動(dòng)態(tài)規(guī)劃算法和漸進(jìn)比對(duì)得到最后的多序列比對(duì)。試驗(yàn)證實(shí)了該方法的有效性。【關(guān)鍵詞】多序列比對(duì)；RNA二級(jí)結(jié)構(gòu)；配對(duì)概率矩陣；結(jié)構(gòu)信息矢量；動(dòng)態(tài)規(guī)劃Abstract：WepresentedaRNAsequencesmulti-alignmentmethodbasedonstructuralinformation.Firstly,wecomputedba
2、sepairingprobabilityofeverysequencebythermodynamicmethod.Secondly,thestructuralinformationvectorwasconstructedthroughgottenstructureinformationandbeenpairalignmenteachother,asresult,aguidetreewasconstructed.Finally,combinetraditionalsequencealignment,wepresentedtheobjectivefunctionandgotthefi
3、nalmulti-alignmentbydynamicprogrammingalgorithmandprogressivealignmentwithguidetree.Wetestvalidityofourmethodon7sequencesofIREthroughcomparingwithClutalWandT-Coffee.21Keywords：Multiplesequencesalignment;Secondarystructures;Basepairingprobability;Structuralinformationvector;Dynamicprogramminga
4、lgorithm1引言多序列比對(duì)是生物序列分析的基礎(chǔ)，傳統(tǒng)的多序列比對(duì)（如ClustralW［1］、T-Coffee［2］）通常用于數(shù)據(jù)庫搜索或是結(jié)構(gòu)特點(diǎn)探測，但是對(duì)RNA分子，這些方法就不適用了，因?yàn)镽NA分子的功能主要由其二級(jí)結(jié)構(gòu)確定，在進(jìn)化過程中RNA的結(jié)構(gòu)比序列具有更強(qiáng)的保守性，許多RNA有關(guān)的分析研究也正是應(yīng)用了這一特點(diǎn)，如RNA結(jié)構(gòu)分析［3-5］、RNA同源搜索［6］、非編碼RNA探測［7-8］和基于RNA的系統(tǒng)進(jìn)化推斷［9］。而這些RNA序列分析方法都是要求先進(jìn)行準(zhǔn)確的多序列比對(duì)，這里的準(zhǔn)確，就是指序列比對(duì)不僅要考慮序列信息，而且要更多的考慮結(jié)構(gòu)信息。21基于序列和
5、結(jié)構(gòu)信息的RNA多序列比對(duì)一般可以分為兩類［10］：概率方法和非概率方法。概率方法基于上下文無關(guān)語法（SCFG），要求一個(gè)初始比對(duì)作為輸入，而輸出的質(zhì)量對(duì)初始比對(duì)的依靠性較強(qiáng)。該方法被用于對(duì)RNA家族進(jìn)行建?；蚴峭ㄟ^比較分析來預(yù)測二級(jí)結(jié)構(gòu)，比如Cove［11］、RNACAD［12］和Pfold［4］。非概率方法，像MARNA［10］，RNAlign［13］，PMmulti［14］，這種方法先進(jìn)行雙序列比對(duì)，然后漸進(jìn)的完成多序列比對(duì)。我們提出的方法屬于后者。2算法Sankoff［15］首先提出同時(shí)進(jìn)行序列比對(duì)和結(jié)構(gòu)預(yù)測，但是該算法的時(shí)間復(fù)雜度為O(N6)，空間復(fù)雜度為O(N4)，其
6、中N為序列長度。已有的幾個(gè)采用此方法的程序都使用了不同的限制，比如，F(xiàn)oldalign［16］利用了核心比對(duì)和貪婪算法，而Dynalign［17］則是通過限制兩個(gè)序列間的最大距離來減少復(fù)雜度。我們采用類似Sankoff算法的思路，但不是為了同時(shí)進(jìn)行序列比對(duì)和結(jié)構(gòu)預(yù)測，只是為了得到考慮結(jié)構(gòu)信息的多序列比對(duì)?；静襟E是：首先，對(duì)每條序列，分別計(jì)算出其堿基配對(duì)概率矩陣，然后將這些矩陣變換成易于比較的結(jié)構(gòu)信息矢量，通過兩兩比對(duì)這些矢量，構(gòu)造出一個(gè)比對(duì)指導(dǎo)樹，最后根據(jù)比對(duì)指導(dǎo)樹，漸進(jìn)的得到多序列比對(duì)。2.1堿基對(duì)配對(duì)概率矩陣為了得到配對(duì)概率矩陣，首先要進(jìn)行劃分函數(shù)的計(jì)算，McCaskill
7、［18］給出了RNA二級(jí)結(jié)構(gòu)的劃分函數(shù)的概念。RNA二級(jí)結(jié)構(gòu)的劃分函數(shù)Q定義為：21Q=∑Se-△G(S)/RT(1)式中，ΔG是結(jié)構(gòu)的Gibbs自由能變化量，R是氣體常數(shù)，T是絕對(duì)溫度，S是所有可能二級(jí)結(jié)構(gòu)的集合。McCaskill提出了一種動(dòng)態(tài)規(guī)劃算法來確定二級(jí)結(jié)構(gòu)形成中的劃分函數(shù)，該算法給出了序列中每個(gè)可能堿基對(duì)的配對(duì)概率，用一個(gè)概率點(diǎn)圖顯示，程序RNAfold［20-21］就是采用的這種算法。因?yàn)閷?duì)能量規(guī)則進(jìn)行了簡化，對(duì)多分支環(huán)的處理是用單鏈堿基的自由能來模擬堿基堆積間的
