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

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

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

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

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ù)下，算法的精度有所提高?；谛蛄斜葘χ械南嗨贫染仃?，提出了一種蛋白質(zhì)關(guān)聯(lián)圖的相似度矩陣表示，并用Greedy-EO混合算法求解基于關(guān)聯(lián)圖的蛋白質(zhì)結(jié)構(gòu)比對問題(關(guān)聯(lián)圖重疊問題CMO)。算法首先基于關(guān)聯(lián)圖相似度矩陣，應(yīng)用貪婪算法得到問題的初始解，然后采用極值優(yōu)化算法得到問題的近優(yōu)解。相似度矩陣

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