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

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

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

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