生物序列比對(duì)算法的并行優(yōu)化設(shè)計(jì)與實(shí)現(xiàn).pdf

1、生物序列比對(duì)是生物信息學(xué)的基礎(chǔ)和核心，隨著生命科學(xué)的迅猛發(fā)展，需要研究的蛋白質(zhì)和核酸序列的信息顯著增加。常見(jiàn)的雙序列比對(duì)串行算法時(shí)間復(fù)雜度為O(N2)，多序列比對(duì)時(shí)間復(fù)雜度更高，隨著序列長(zhǎng)度的增加和比對(duì)規(guī)模的擴(kuò)大，時(shí)間開(kāi)銷難以接受。在此情況下如果能夠挖掘算法的潛在并行性，通過(guò)數(shù)據(jù)劃分、流水處理等方式將算法并行化，使其在多個(gè)處理器上并行執(zhí)行，可以大大提升算法效率。
　　本文首先對(duì)生物序列比對(duì)和并行算法的相關(guān)概念進(jìn)行了介紹。采取流水處

2、理方式，將Needleman-Wunsch算法進(jìn)行并行化設(shè)計(jì)。在此基礎(chǔ)上提出了多個(gè)序列比對(duì)算法的并行化方法。通過(guò)找到多個(gè)checkpoint將矩陣劃分若干部分，為每個(gè)處理器分配矩陣的一個(gè)部分，使各處理器并行執(zhí)行子矩陣的Hirschberg算法并對(duì)完成后的結(jié)果進(jìn)行整合，將Hirschberg算法進(jìn)行并行化；通過(guò)提出使用活動(dòng)結(jié)點(diǎn)和活動(dòng)結(jié)點(diǎn)鏈表創(chuàng)建后綴樹(shù)的方法，使按分支并行構(gòu)建后綴樹(shù)和按分支獲取最大唯一匹配可以并行執(zhí)行并且擺脫了對(duì)后綴鏈表的依

3、賴，之后并行對(duì)錨點(diǎn)間的空位進(jìn)行合并，將MUMmer算法進(jìn)行并行化；通過(guò)對(duì)角線并行方式并行獲取和擴(kuò)展熱點(diǎn)區(qū)域，采取將距離矩陣進(jìn)行分塊方式使多處理器并行獲取不同對(duì)角線上熱點(diǎn)區(qū)域的距離長(zhǎng)度，將 FASTA算法進(jìn)行并行化；通過(guò)距離矩陣分塊方式并行獲取序列兩兩比對(duì)的距離長(zhǎng)度，以及并行從進(jìn)化樹(shù)的葉子向根進(jìn)行合并的方式，將ClustalW算法進(jìn)行了并行化。
　　最后對(duì)上述4種算法及并行化算法分別進(jìn)行了實(shí)現(xiàn)，將串行算法運(yùn)行時(shí)間與雙核及四核條件下并