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

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

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