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

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