CUDA計(jì)算技術(shù)在生物序列數(shù)據(jù)處理中的應(yīng)用研究.pdf

1、目前新的高通量DNA測(cè)序技術(shù)能夠在很短的時(shí)間內(nèi)以較低的成本生成大量的序列數(shù)據(jù)，生物序列的數(shù)據(jù)量正以爆炸式的速度快速增長(zhǎng)。與此同時(shí)，計(jì)算機(jī)處理器的頻率已接近理論極限，這意味著現(xiàn)存的串行算法很難像以前一樣依靠頻率的提高獲得性能提升。并行處理技術(shù)成為解決這一效率差異的必然選擇之一。由于GPU比CPU擁有更強(qiáng)的計(jì)算能力和更高的內(nèi)存帶寬，而生物序列數(shù)據(jù)又具有數(shù)據(jù)量大、數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單的特點(diǎn)，本文采用基于數(shù)據(jù)并行處理指令體系的GPU眾核計(jì)算技術(shù)來(lái)實(shí)現(xiàn)生

2、物序列數(shù)據(jù)的廉價(jià)高效處理。本文根據(jù)復(fù)雜程度的不同，精心篩選出若干個(gè)經(jīng)典序列分析問(wèn)題作為并行處理的研究對(duì)象，分別給出高效的數(shù)據(jù)并行算法設(shè)計(jì)，并通過(guò)CUDA并行計(jì)算平臺(tái)加以實(shí)現(xiàn)、分析和優(yōu)化。本文的主要貢獻(xiàn)總結(jié)如下:
　　第一，對(duì)CUDA計(jì)算涉及的軟硬件并行體系結(jié)構(gòu)特點(diǎn)進(jìn)行了比較全面的研究?；贕PU屬于SIMD并行指令體系的特點(diǎn)，總結(jié)并歸納了常用的基本數(shù)據(jù)并行操作，為并行算法的設(shè)計(jì)和實(shí)現(xiàn)提供了基本的參考和指南。
　　第二，針對(duì)生

3、物序列分析研究中最基本的開(kāi)放閱讀框架問(wèn)題，通過(guò)運(yùn)用直接和間接并行化兩種方法，完成了六讀碼框翻譯算法和序列頻率統(tǒng)計(jì)算法的高效數(shù)據(jù)并行設(shè)計(jì)與實(shí)現(xiàn)，展示了數(shù)據(jù)并行算法設(shè)計(jì)的特點(diǎn)以及GPU通用計(jì)算技術(shù)的優(yōu)勢(shì)和局限，并給出了GPU計(jì)算的并行加速模型，用以衡量并行化效率。本文基于直接轉(zhuǎn)換的方法設(shè)計(jì)了具有高度并行性的適合于GPU執(zhí)行的六讀碼框翻譯算法，其執(zhí)行速度要比串行算法快5倍左右。然而序列頻率統(tǒng)計(jì)過(guò)程的并行化就無(wú)法這么自然的表達(dá)，因?yàn)檫@個(gè)過(guò)程中包

4、含嚴(yán)重的并行訪問(wèn)沖突和延遲，只能采用以排序和計(jì)算前置和操作進(jìn)行替代的間接并行化方法。該間接并行頻率統(tǒng)計(jì)算法基本能夠達(dá)到相應(yīng)串行算法的效率。并行開(kāi)放閱讀框架算法總的執(zhí)行效率為串行算法的2倍左右。
　　第三，針對(duì)序列測(cè)定和分析中的重復(fù)序列檢測(cè)問(wèn)題，提出了一種通過(guò)構(gòu)造字典次序來(lái)快速完成超短精確重復(fù)查找的數(shù)據(jù)并行算法，該算法的效率要比目前的串行算法提高一個(gè)數(shù)量級(jí)。DNA序列中的重復(fù)區(qū)域?qū)υS多關(guān)鍵生物功能發(fā)揮著至關(guān)重要的作用，重復(fù)序列檢測(cè)也

5、是生物信息學(xué)中一個(gè)必須解決的基本問(wèn)題。本文詳細(xì)說(shuō)明了一個(gè)基于CUDA平臺(tái)的快速數(shù)據(jù)并行超短精確重復(fù)查找算法的設(shè)計(jì)和實(shí)現(xiàn)過(guò)程，并以這些超短重復(fù)為種子，進(jìn)一步提出了啟發(fā)式的海明距離和編輯距離重復(fù)測(cè)定的數(shù)據(jù)并行化方法，并給出了可行的并行線程調(diào)度方案。并行重復(fù)查找算法設(shè)計(jì)過(guò)程中采用的按串行代碼功能區(qū)逐步完成并行化的方法，不但可以快速確定并行化過(guò)程中面臨的瓶頸問(wèn)題，進(jìn)而判定整個(gè)算法的并行化難度，而且便于并行程序的設(shè)計(jì)、調(diào)試、分析和優(yōu)化，可以作為現(xiàn)

6、存大多數(shù)串行算法實(shí)現(xiàn)并行化處理的參考。
　　第四，針對(duì)后綴數(shù)組構(gòu)造問(wèn)題，提出了一種新的以排序方法替代傳統(tǒng)分組策略的并行后綴數(shù)組倍增構(gòu)造算法，其數(shù)據(jù)并行執(zhí)行效率明顯高于同類(lèi)串行算法。后綴數(shù)組廣泛應(yīng)用于序列分析、字符串匹配和文本壓縮等領(lǐng)域，近年來(lái)，有關(guān)后綴數(shù)組構(gòu)造和應(yīng)用算法的不斷探索構(gòu)成了計(jì)算機(jī)科學(xué)中一個(gè)非常活躍的研究領(lǐng)域。在對(duì)現(xiàn)有串行算法進(jìn)行了全面的分析和對(duì)比之后，通過(guò)抽象和等效替換的方法提出了一種適合于GPU計(jì)算的且更為簡(jiǎn)潔的并行