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

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

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

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