帶相交作用結(jié)構(gòu)的折疊問題.pdf

1、在本文中，我們首先在第2章介紹了一個以均勻概率生成k不相交，模塊圖的算法。這個算法能在經(jīng)過0（nk）的時間和空間復(fù)雜度的預(yù)處理后，以O(shè)(n)的時間和空間復(fù)雜度產(chǎn)生k不相交，σ模塊圖。其次我們把注意力集中在單鏈的核糖核酸序列的折疊問題上。在第3章中，我們給出一個產(chǎn)生3不相交標(biāo)準(zhǔn)的最小自由能(mfe)核糖核酸結(jié)構(gòu)的折疊算法，cross。這里如果一個核糖核酸結(jié)構(gòu)不含有3條互相相交的弧，則我們稱這個結(jié)構(gòu)是3不交的。如果一個核糖核酸結(jié)構(gòu)中的棧長度

2、大于等于2，則我們稱這個結(jié)構(gòu)是標(biāo)準(zhǔn)的。我們用到的最小自由能是基于圈的能量參數(shù)和一種特殊的偽扭結(jié)能量參數(shù)。這個算法可以分為三個部分：首先遞歸地構(gòu)造motifs和與之相關(guān)的shadows，其次以這些shadows為根生成skeleta樹，最后以動態(tài)規(guī)劃的方法對skeleta進行填充。
　　 在第4章中，我們應(yīng)用了一種對核糖核酸結(jié)構(gòu)的自然的拓撲分類，這種分類是基于嵌在給定虧格曲面上的不可約分支。我們在將虧格1的結(jié)構(gòu)以二級結(jié)構(gòu)的方法互相

3、迭代以產(chǎn)生更高虧格數(shù)的結(jié)構(gòu)。一個相應(yīng)明確的多重上下文無關(guān)的語法給出了一個有效求最小能量，配分函數(shù)和隨機樣本的動態(tài)規(guī)劃算法。我們得出了相比以前現(xiàn)存的算法，引入一個與拓撲相關(guān)的偽扭結(jié)懲罰參數(shù)可以改進堿基配對預(yù)測中10％到20%的敏感度和正預(yù)測值。
　　 然后在第5章中，我們研究了核糖核酸．核糖核酸互相作用的問題，在這個問題上我們同時考慮兩條核糖核酸序列。核糖核酸-核糖核酸互相作用問題(RIP)是研究兩個核糖核酸分子互相結(jié)合時的最優(yōu)能

4、量結(jié)構(gòu)。我們在一種名為“緊結(jié)構(gòu)”的概念上計算配分函數(shù)。這個動態(tài)規(guī)劃方法被完全成熟地應(yīng)用到計算基因匹配概率上。把hybrid作為分解的單元后我們可以計算給定核糖核酸與目標(biāo)核糖核酸中任意位置相作用的概率。再加上核糖核酸．核糖核酸互相作用結(jié)構(gòu)的Boltzmann整體加權(quán)隨機取樣，hybrid概率的計算變得更完整了。這個O(N6)時間復(fù)雜度和0(N4)空間復(fù)雜度的算法被寫成rip2工具，并且對現(xiàn)今小型細菌中的核糖核酸相互作用結(jié)構(gòu)已經(jīng)足夠有效了。

5、
　　 最后，我們在3不相交標(biāo)準(zhǔn)核糖核酸結(jié)構(gòu)基礎(chǔ)上分析了核糖核酸序列-結(jié)構(gòu)的關(guān)系。這些結(jié)構(gòu)是用在第3章中提到的算法cross來折疊的。我們在第6中給出很多關(guān)于將核糖核酸序列映射到3不相交標(biāo)準(zhǔn)核偽扭結(jié)糖核酸結(jié)構(gòu)的結(jié)構(gòu)性的結(jié)果。我們研究了一些性質(zhì)，例如偽扭結(jié)結(jié)構(gòu)的分?jǐn)?shù)，突出的偽扭結(jié)形狀，中立的步行，中立的鄰點和局部連通性。我們的結(jié)果顯示，與核糖核酸二級結(jié)構(gòu)相類似，3不相交偽扭結(jié)核糖核酸結(jié)構(gòu)給出一種合適的分子顯型，特別是在中立進化里。

6、我們可以斷言一種對帶偽扭結(jié)核糖核酸的擴展?jié)B透中立網(wǎng)絡(luò)是存在的。
　　 cross的源代碼可以在www.combinatorics．cn/cbpc/cross.html找到。rip2的源代碼可以在bttp://www．combinatorics．cn/cbpc/rip2．html或bttp://www．bioinf.uni-leipzig.de/Software/rip.html下載到。gfold的源代碼可以在http://www