基于集群式超級計算機(jī)的三序列比對算法的并行實(shí)現(xiàn)及研究.pdf

1、序列比對算法用在許多不同的領(lǐng)域。當(dāng)前，這些領(lǐng)域里面的一個重要應(yīng)用就是比對大分子，例如比對DNA和蛋白質(zhì)序列，以及蛋白質(zhì)結(jié)構(gòu)比較?；旧?，所有的序列比對算法，或多或少都會用到Needleman和Wunsch(1970)的動態(tài)規(guī)劃算法。雖然從理論上來說用兩兩比對的方法來實(shí)現(xiàn)多序列比對是非常簡單方便的，但是，盡管目前人們做了大量的工作和努力，對于6條以上的多序列比對，用兩兩比對的方法是不現(xiàn)實(shí)的。而且對于屬于NP難問題的多序列比對問題，任何試圖

2、找到一種快速的計算優(yōu)化比對的方法的企圖都很有可能要失敗的。為了提高優(yōu)化比對的算法，全世界的科技工作者都馬不停蹄地在辛苦地工作。這樣就產(chǎn)生了許許多多的近似優(yōu)化比對的偽算法，同時也開發(fā)出一大堆應(yīng)用程序。 許多情況下，都有必要同時比對三序列。DavidR.Powell提出了一種新的使用線性空位罰分的優(yōu)化的三序列比對算法。這個算法最早是由Ukkonen基于兩序列和簡單打分而提出的。本文基于分治法的原理通過引入“檢查點(diǎn)法”對其進(jìn)行改進(jìn)，并