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

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

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

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

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

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

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

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

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