DNA序列比對中基于AVX指令集的BWT算法研究.pdf

1、在生物信息學領域，生物基因的序列比對一直是科學研究的熱門問題之一。隨著生物學的發(fā)展與對物種研究的深入，基因數(shù)據(jù)日益增多。同時新一代測序技術的出現(xiàn)，測序時間和成本下降、測序通量高使序列數(shù)據(jù)顯著增加，呈指數(shù)形式增長趨勢，并且每天仍有新的生物基因序列數(shù)據(jù)被發(fā)現(xiàn)和記錄，而數(shù)據(jù)產(chǎn)生的速度遠大于數(shù)據(jù)處理的速度，因此對大規(guī)模DNA測序數(shù)據(jù)的處理亟待更高效的方法。對海量數(shù)據(jù)進行及時有效的處理、分析，對于揭示其內(nèi)涵、闡明和理解其所蘊含的生物學意義、得到對

2、人類有用的信息具有重要意義。序列比對作為基因數(shù)據(jù)研究的基礎問題，能夠為后續(xù)基因組計劃等研究提供重要信息，因此提高測序數(shù)據(jù)的序列比對速度至關重要。
　　本文通過對已有序列比對算法的研究，針對目前基于BWT(Burrows-Wheeler Transform)索引技術的比對軟件比對準確率高且內(nèi)存消耗小，較其他基于哈希表的方法性能優(yōu)越，但存在訪存次數(shù)多，時間消耗較大的問題，就如何提高BWT索引技術的序列比對速度進行研究，提出一種應用基于

3、Intel微架構的AVX(Advanced vector Extensions)指令技術，從改進原有算法內(nèi)部函數(shù)運算方式的角度進行單線程并行優(yōu)化的方法，對BWT算法中計算量大、多次遞歸調(diào)用的函數(shù)進行改寫，減少函數(shù)運算次數(shù)及CPU訪存次數(shù)，提高算法執(zhí)行效率，實現(xiàn)提高BWT算法序列比對速度、降低算法時間消耗的目的。
　　本文設計并實現(xiàn)了基于AVX指令集優(yōu)化的BWT序列比對算法，在對BWT算法的代碼及實現(xiàn)過程進行深入研究之后，找到適于A

4、VX指令對代碼改寫的部分。將occ函數(shù)結果全部計算出來并存在內(nèi)存中，在計算時使用AVX指令集的計算方式進行計算，使計算機能夠一條指令并行執(zhí)行多次計算，極大縮短算法運行時間。為驗證比對結果的準確性和速度比，本文采用大豆測序數(shù)據(jù)對算法進行實驗。實驗結果表明，本文提出的指令改進有效提高了算法的查找效率，加快了序列比對速度。在接近源碼比對準確率的同時提高比對速度近50％，使算法時間性能得到顯著提升，實現(xiàn)序列比對在算法改寫方向的并行優(yōu)化。