基于格點(diǎn)和關(guān)聯(lián)圖模型的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)與比對(duì)算法研究.pdf

1、后基因組時(shí)代研究的核心內(nèi)容之一就是闡明蛋白質(zhì)的功能，因?yàn)榈鞍踪|(zhì)是生理功能的執(zhí)行者以及生命現(xiàn)象的體現(xiàn)者。研究表明，蛋白質(zhì)的生物功能由蛋白質(zhì)的結(jié)構(gòu)所決定，因此在研究蛋白質(zhì)時(shí)需要了解蛋白質(zhì)的空間結(jié)構(gòu)。然而，受到蛋白質(zhì)結(jié)構(gòu)和功能獲取實(shí)驗(yàn)技術(shù)的限制，已知序列的蛋白質(zhì)遠(yuǎn)遠(yuǎn)多于已知結(jié)構(gòu)和功能的蛋白質(zhì)。因此理論預(yù)測(cè)蛋白質(zhì)結(jié)構(gòu)與功能的方法不斷涌現(xiàn)。本文從優(yōu)化算法設(shè)計(jì)角度出發(fā)，研究了基于格點(diǎn)模型的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問(wèn)題，基于蛋白質(zhì)關(guān)聯(lián)圖的結(jié)構(gòu)預(yù)測(cè)和結(jié)構(gòu)比對(duì)問(wèn)題

2、。主要工作如下：
　　 基于優(yōu)化理論的思想，分別建立了二維(2D)和三維(3D)疏水，親水(HP)格點(diǎn)模型。對(duì)于2DHP模型，提出了一種GA-EO混合算法求解蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問(wèn)題。算法以遺傳算法(Genetic Alagorithm)為框架，極值優(yōu)化(Extremal Optimization)作為變異算法。對(duì)于3DHP模型，提出了一種EO-PERM混合算法求解蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問(wèn)題。算法以極值優(yōu)化(EO)為框架，增長(zhǎng)型算法PERM(

3、pruned-enriched Rosenbluth method)為鄰域搜索策略。在極值優(yōu)化算法中，分別給出了適合2DHP和3DHP模型的局部適應(yīng)度定義。測(cè)試的結(jié)果表明：在一定規(guī)模下，混合算法可以找到測(cè)試序列在格點(diǎn)上的最低能量狀態(tài)。
　　 引入了一種改進(jìn)的COMAR算法來(lái)求解基于關(guān)聯(lián)圖的蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)問(wèn)題。算法首先根據(jù)蛋白質(zhì)關(guān)聯(lián)圖和先驗(yàn)知識(shí)以半隨機(jī)的方式生成距離信息，然后根據(jù)距離信息得到蛋白質(zhì)的坐標(biāo)表示，最后通過(guò)坐標(biāo)修正和攝動(dòng)

4、使得重構(gòu)結(jié)構(gòu)的關(guān)聯(lián)圖與給定的關(guān)聯(lián)圖相一致。結(jié)果表明閾值較大的關(guān)聯(lián)圖重建的結(jié)構(gòu)比閾值小的要好。此外，改進(jìn)COMAR算法與原COMAR算法在相同的達(dá)代次數(shù)下，算法的精度有所提高?；谛蛄斜葘?duì)中的相似度矩陣，提出了一種蛋白質(zhì)關(guān)聯(lián)圖的相似度矩陣表示，并用Greedy-EO混合算法求解基于關(guān)聯(lián)圖的蛋白質(zhì)結(jié)構(gòu)比對(duì)問(wèn)題(關(guān)聯(lián)圖重疊問(wèn)題CMO)。算法首先基于關(guān)聯(lián)圖相似度矩陣，應(yīng)用貪婪算法得到問(wèn)題的初始解，然后采用極值優(yōu)化算法得到問(wèn)題的近優(yōu)解。相似度矩陣

5、由蛋白質(zhì)殘基特征的相似度組成，它是產(chǎn)生初始解的重要依據(jù)，也是極值優(yōu)化算法中鄰域搜索的準(zhǔn)則。一共采用了五種策略定義相似度矩陣。與多項(xiàng)式時(shí)間近似算法PTAS方法比較，算法速度快，解的質(zhì)量也有所提高。與分支縮減算法比較，所得的相似性指標(biāo)互有高低。受TOPS模型的啟發(fā)，提出了蛋白質(zhì)關(guān)聯(lián)圖的等價(jià)向量表示，并用Hungarian-EO混合算法求解CMO問(wèn)題。算法首先引入向量集合來(lái)等價(jià)表示蛋白質(zhì)關(guān)聯(lián)圖，然后計(jì)算關(guān)聯(lián)圖的相似度矩陣，接著構(gòu)造基于相似度矩