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

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

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

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

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