分散式記憶體環境下三條序列比對技術的研發

序列比對是計算生物學相當重要的研究課題，在1970年，Needleman and Wunsch 首先提出以動態程式規劃技術來比對兩條全長序列，自此，相當多的研究主要著重於兩條序列比對的方法，利用動態程式規劃技術，傳統的兩條序列比對方法可以在時間及空間複雜度O(n2)內完成，D.S. Hirschberg (1975) 提出了一個線性空間的演算法將兩條序列比對演算法的空間複雜度由O(n2)降為O(n)，不過，時間複雜度仍限制了長序列使用上的需求，過去，利用平行處理的技術來降低兩條序列比對演算法的複雜度是一個相當有效的方法，Rajko and Aluru (2004) 提出了一個有效率的兩條序列比對演算法，該演算法可以求得時間跟空間最佳的複雜度，將先前的時間及空間的複雜度由O(n2)及O(n)降為O(n2/p)及O(n/p)。因為利用動態程式規劃技術來求多序列比對的最佳解是一個NP-hard問題，目前大多數的多序列比對演算法都是基於兩條序列比對的結果，並透過一個指導樹(Guide Tree)來加以整合。三條序列比對演算法在過去亦有部份的研究成果被提出，Murata et al. (1985) 提出了一個三條序列比對的演算法，並證明三條序列比對的結果有可能優於兩條序列比對的結果，不過，他所提出的方法其時間及空間複雜度皆為O(n3)，後來，X. Huang (1993)利用Hirschberg的演算法將三條序列比對演算法的空間複雜度降為O(n2)，Yue and Tang (2007)亦提出類似的研究成果，Kruspe and Stadler (2007) 更進一步的提出基於三條序列比對結果的多條序列比對演算法，而Hung et al (2007) 也提出基於兩條與三條序列比對結果的多條序列比對演算法，其研究成果指出三條序列比對的結果有助於提升序列比對的正確性，不過，上述的方法皆需O(n3)的時間複雜度，目前並無有效率的平行演算法被提出，因此，本計畫最主要是要提出一個有效率的三條序列比對平行演算法，在這個計畫年度中，我們的工作項目主要可以分成五個部分：第一個部分是發展一個平行化的三條序列比對演算法，包含發展資料切割、資訊傳輸、管線計算等技術，第二個部分是將Hirschberg的演算法融入所發展的三條序列比對演算法，希望進一步的降低空間上的需求，上述兩個部份預期將提出一個時間及空間複雜度為O(n3/p)及O(n2/p)的平行演算法，然而，針對超長序列，上述的方法仍無法滿足其空間上的需求，因此，第三個部份是希望能發展切斷點的技術，將超長序列加以切割，分開進行三條序列比對後，再合併其結果，一個好的切斷點技術將能保證得到不錯的結果。第四個部分，我們將針對所開發出來的技術來建構其理論模組及效能評估函式，用來評估與分析不同的生物序列對所發展技術的效能。第五個部分，將針對其前面所發展出的技術和理論做實際上的測試和實作，並且，可以依照所測試的結果來結合第四部分所建立的理論模組及效能評估函式來做分析。

系統編號:PB9706-2177
原計畫編號:NSC97-2218-E182-003