基于AFP的序列無關(guān)蛋白質(zhì)結(jié)構(gòu)比對算法研究.pdf

1、隨著被譽為人類科學(xué)“登月計劃”的人類基因組項目的順利完成，生命科學(xué)進入了一個嶄新的時代--“后基因時代”?；蛐蛄械墨@得一方面為人們理解生物體的奧秘提供了基礎(chǔ)，但同時人們也發(fā)現(xiàn)單從基因序列的角度并不能完整系統(tǒng)的闡述生物功能。蛋白質(zhì)是生命體構(gòu)成的主要成分，同時也是生命活動的主要執(zhí)行者，對于理解生物體的內(nèi)在功能具有重要的指導(dǎo)意義。
　　尋找蛋白質(zhì)結(jié)構(gòu)之間的相似性有利于讓人們理解功能之間的相似性，發(fā)現(xiàn)遠(yuǎn)程的同源關(guān)系，甚至發(fā)現(xiàn)蛋白質(zhì)結(jié)構(gòu)的

2、進化機制。因此，尋找蛋白質(zhì)相似性的手段--蛋白質(zhì)結(jié)構(gòu)比對應(yīng)運而生，并且發(fā)展為生物信息學(xué)不可或缺的一種工具。越來越多的蛋白質(zhì)結(jié)構(gòu)比對算法已經(jīng)被提出，例如FATCAT，CE等。但是，許多蛋白質(zhì)結(jié)構(gòu)比對算法都是基于序列性限制的，并不能檢測到由于循環(huán)置換或是不同祖先進而來的蛋白質(zhì)結(jié)構(gòu)之間的序列無關(guān)相似性。
　　基于上述背景，本文簡要的介紹了當(dāng)前主流的七種序列無關(guān)蛋白質(zhì)結(jié)構(gòu)比對算法，并且提出了一種新的基于變長AFP的序列無關(guān)蛋白質(zhì)結(jié)構(gòu)比對算

3、法。與其他基于AFP的蛋白質(zhì)結(jié)構(gòu)比對算法不同的是我們的算法采用的AFP是變長的，這樣不僅可以更好的表征蛋白質(zhì)局部結(jié)構(gòu)，而且可以提高運算速率。此外，我們利用AFP的空間信息對AFP進行篩選，剔除含有噪聲的AFP，從而獲得高質(zhì)量的AFP。我們將高質(zhì)量的AFP之間的關(guān)系用圖論的理論處理，并用這個圖的一個優(yōu)質(zhì)的最大團來表示初始結(jié)構(gòu)對齊。最后，為了避免動態(tài)規(guī)劃算法在序列無關(guān)結(jié)構(gòu)比對中的局限性，我們采用貪心算法對初始對齊進行優(yōu)化并得到最終的比對結(jié)果