基于de Bruijn圖的DNA多序列比對并行算法研究.pdf

1、多序列比對是目前生物信息領域研究的重要課題之一,在基因識別、蛋白質結構預測等領域有著廣泛的應用。由于問題本身所固有的復雜性,至今還沒有一個令人滿意的算法,同時隨著生物數(shù)據(jù)的不斷增長,串行算法已不能滿足人們的需求。本課題重點研究了如何利用de Brujin圖進行多序列比對及其并行化處理方案,提出了一個新的多序列比對并行算法PL_GAlign。課題的主要工作與貢獻.如下:
　　 在基于圖論的算法中引入了距離參數(shù)并采用了改進的星形比對

2、算法:詳細分析了目前使用比較廣泛的多序列比對算法,但是常用的并行劃分策略對該類算法的執(zhí)行效果較差。因此重點研究了基于圖論的多序列比對算法并對其進行了改進:為了更好的適應基因的變異性,在該類算法中引入了距離參數(shù)d,將現(xiàn)有算法的精確匹配修改為允許一定誤差的模糊匹配。在應用 de Bruijn圖得到中心序列后,摒棄了現(xiàn)有算法中常用的動態(tài)規(guī)劃算法,采用了更為適合這種情況的星型比對算法并對其進行了改進,從而使該算法的時間復雜度降低至幾乎線性。

3、r>　　 針對算法中的各個階段提出了并行處理策略:針對多序列比對的高計算復雜性問題,研究了基于 de Bruijn圖的并行化處理方案。分別對基于圖論的多序列比對算法中的構建 de Bruijn圖、去環(huán)、尋找最大權值路徑和兩兩比對階段的串行處理過程和可并行性進行了探討,提出了各個階段的并行處理策略。
　　 最后進行了一系列數(shù)據(jù)測試,實驗結果證明PL GAlign算法在運行速度上要優(yōu)于現(xiàn)有的迭代法,尤其當輸入序列較長且數(shù)目較多時,