面向新一代測(cè)序的GPU序列比對(duì)工具研究.pdf

1、生物序列比對(duì)是生物信息學(xué)研究中的基本方法。隨著新一代測(cè)序技術(shù)的飛速發(fā)展,以及宏基因組學(xué)、表觀基因組學(xué)和全基因組關(guān)聯(lián)分析等研究領(lǐng)域和方法的興起,海量的數(shù)據(jù)涌現(xiàn)使得傳統(tǒng)的序列比對(duì)算法無法滿足序列分析處理的需求。研究如何利用最新的計(jì)算機(jī)技術(shù)加速序列比對(duì)具有重要的意義。
　　為了加速序列比對(duì)過程,一種方案是通過改進(jìn)數(shù)據(jù)結(jié)構(gòu)和算法來實(shí)現(xiàn),這些改進(jìn)的方法因序列比對(duì)的類型而異。另一種方案則是采用并行計(jì)算或者輔助加速硬件來實(shí)現(xiàn),這種方案的基本思想

2、大體相同,都是試圖發(fā)掘原始序列比對(duì)算法中的可并行性,其實(shí)際加速效果因而也受限于算法的可并行性。序列比對(duì)算法的并行加速研究主要采用的技術(shù)有并行計(jì)算、分布式計(jì)算和異構(gòu)計(jì)算。利用圖形處理器(graphic processing unit,GPU)用于通用計(jì)算是一種異構(gòu)計(jì)算技術(shù),采用GPU加速序列比對(duì)近些年來受到大量關(guān)注,大量的序列比對(duì)工具已經(jīng)移植到GPU并且取得了較好的加速效果。但是研究人員在選擇序列比對(duì)工具時(shí)是否應(yīng)該選擇這些基于GPU的比對(duì)

3、工具,目前還沒有關(guān)于其可用性的綜合評(píng)價(jià)研究。
　　在生物信息學(xué)研究中,不同的序列比對(duì)工具往往針對(duì)特定的應(yīng)用,第二代測(cè)序技術(shù)對(duì)海量短串的比對(duì)需求催生了大量的短串比對(duì)工具,短串比對(duì)工具可以滿足短串比對(duì)的需求,但是由于多數(shù)短串比對(duì)工具無法進(jìn)行長(zhǎng)串的比對(duì),且在處理序列插入缺失時(shí)性能較差,同時(shí)第三代測(cè)序技術(shù)將使得測(cè)序長(zhǎng)度增長(zhǎng)。對(duì)傳統(tǒng)序列比對(duì)算法的加速研究依然具有重要意義。
　　宏基因組學(xué)源自傳統(tǒng)的微生物基因組學(xué),其直接從環(huán)境樣品中提取

4、全部的微生物基因序列進(jìn)行序列分析和功能分析。宏基因組學(xué)可以用來揭示微生物群落結(jié)構(gòu)和功能的關(guān)系、進(jìn)化關(guān)系、發(fā)現(xiàn)新基因等。在宏基因組分析中,需要對(duì)差異較大的混合基因序列進(jìn)行比對(duì),傳統(tǒng)的序列比對(duì)算法無法滿足海量數(shù)據(jù)的分析需求,而短串比對(duì)算法則無法滿足敏感度的要求,因此需要新的算法。GHOSTM是在GPU上實(shí)現(xiàn)的宏基因組序列比對(duì)工具,其極大加快了序列比對(duì)速度,但是對(duì)于海量的新一代測(cè)序數(shù)據(jù)分析任務(wù),其需要更進(jìn)一步的并行加速。
　　本文主要完

5、成了如下的工作:
　　首先,通過文獻(xiàn)研究的方法,對(duì)基于GPU的序列比對(duì)工具進(jìn)行了可用性的綜合評(píng)價(jià)。已有的基于GPU的序列比對(duì)工具往往過分強(qiáng)調(diào)速度提升,而缺少對(duì)準(zhǔn)確度、性能功耗比、性價(jià)比和編程復(fù)雜度等多方面的考慮。本文從以上幾個(gè)角度出發(fā),綜合評(píng)價(jià)了GPU用于序列比對(duì)的可用性。并且進(jìn)一步采用實(shí)際數(shù)據(jù),基于相同的硬件平臺(tái),對(duì)基于GPU的短串比對(duì)工具進(jìn)行了測(cè)試。對(duì)多數(shù)數(shù)據(jù)集,基于GPU的短串比對(duì)工具基本都能夠取得較好的性能功耗比和性價(jià)比,

6、但是允許空位比對(duì)需要更多的優(yōu)化工作。
　　第二,采用計(jì)算統(tǒng)一設(shè)備架構(gòu)(compute unified device architecture,CUDA)并行計(jì)算架構(gòu),對(duì)核酸序列比對(duì)工具BLASTN進(jìn)行并行加速研究,設(shè)計(jì)實(shí)現(xiàn)了CUDA-BLASTN。BLASTN是目前廣泛使用的序列比對(duì)工具-基本局部比對(duì)搜索工具(Basic Local Alignment Search Tool,BLAST)的子工具,其在非編碼RNA研究、生物進(jìn)化研

7、究、未知病原體檢測(cè)研究等領(lǐng)域中發(fā)揮著重要作用?；谟ミ_(dá)(NVIDIA)的CUDA架構(gòu),我們從GPU內(nèi)粗粒度的多線程并行和多GPU并行兩個(gè)維度對(duì)BLASTN的種子查找階段和不允許空位延伸階段進(jìn)行并行加速。CUDA-BLASTN充分利用了CUDA內(nèi)部不同存儲(chǔ)器的特點(diǎn)來實(shí)現(xiàn)加速,相比最新版NCBI-BLASTN,取得了一定的加速效果。CUDA-BLASTN特別適用于中長(zhǎng)查詢序列對(duì)長(zhǎng)序列數(shù)據(jù)庫(kù)的比對(duì)任務(wù)。
　　第三,分別采用傳統(tǒng)并行計(jì)算

8、技術(shù)消息傳遞接口(Message Passing Interface,MPI)技術(shù)和最新分布式計(jì)算架構(gòu)Hadoop對(duì)用于宏基因組學(xué)研究的序列比對(duì)工具GHOSTM進(jìn)行了并行加速。宏基因組學(xué)在未知病原體檢測(cè)等研究中發(fā)揮重要作用,而MPI和Hadoop則是集群計(jì)算環(huán)境和云計(jì)算環(huán)境的基礎(chǔ),為海量數(shù)據(jù)的宏基因組研究提供了計(jì)算環(huán)境的軟件支撐。MPI能夠提供顯式并行,因此我們實(shí)現(xiàn)的mpiGHOSTM的加速比基本隨進(jìn)程數(shù)目線性增加。Hadoop則在單節(jié)

9、點(diǎn)失效后恢復(fù)和可擴(kuò)展性上具有顯著優(yōu)勢(shì),在Hadoop與CUDA整合研究的基礎(chǔ)上,我們實(shí)現(xiàn)了Hadoop-GHOSTM,其能夠充分利用CPU與GPU資源實(shí)現(xiàn)并行加速。
　　本文的主要貢獻(xiàn)有:
　　(1)首次從準(zhǔn)確度、性能功耗比、性價(jià)比和編程復(fù)雜度四個(gè)角度對(duì)基于GPU的序列比對(duì)工具進(jìn)行了綜合評(píng)價(jià),系統(tǒng)地評(píng)價(jià)了GPU用于序列比對(duì)的可用性。
　　(2)基于CUDA并行計(jì)算架構(gòu),對(duì)核酸序列比對(duì)工具BLASTN進(jìn)行了并行加速,服務(wù)