目前新的高通量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ù)來實(shí)現(xiàn)生物序列數(shù)據(jù)的廉價(jià)高效處理。本文根據(jù)復(fù)雜程度的不同,精心篩選出若干個(gè)經(jīng)典序列分析問題作為并行處理的研究對(duì)象,分別給出高效的數(shù)據(jù)并行算法設(shè)計(jì),并通過CUDA并行計(jì)算平臺(tái)加以實(shí)現(xiàn)、分析和優(yōu)化。本文的主要貢獻(xiàn)總結(jié)如下： 第一,對(duì)CUDA計(jì)算涉及的軟硬件并行體系結(jié)構(gòu)特點(diǎn)進(jìn)行了比較全面的研究。基于GPU屬于SIMD并行指令體系的特點(diǎn),總結(jié)并歸納了常用的基本數(shù)據(jù)并行操作,為并行算法的設(shè)計(jì)和實(shí)現(xiàn)提供了基本的參考和指南。 第二,針對(duì)生物序列分析研究中最基本的開放閱讀框架問題,通過運(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ì)過程的并行化就無(wú)法這么自然的表達(dá),因?yàn)檫@個(gè)過程中包含嚴(yán)重的并行訪問沖突和延遲,只能采用以排序和計(jì)算前置和操作進(jìn)行替代的間接并行化方法。該間接并行頻率統(tǒng)計(jì)算法基本能夠達(dá)到相應(yīng)串行算法的效率。并行開放閱讀框架算法總的執(zhí)行效率為串行算法的2倍左右。 第三,針對(duì)序列測(cè)定和分析中的重復(fù)序列檢測(cè)問題,提出了一種通過構(gòu)造字典次序來快速完成超短精確重復(fù)查找的數(shù)據(jù)并行算法,該算法的效率要比目前的串行算法提高一個(gè)數(shù)量級(jí)。DNA序列中的重復(fù)區(qū)域?qū)υS多關(guān)鍵生物功能發(fā)揮著至關(guān)重要的作用,重復(fù)序列檢測(cè)也是生物信息學(xué)中一個(gè)必須解決的基本問題。本文詳細(xì)說明了一個(gè)基于CUDA平臺(tái)的快速數(shù)據(jù)并行超短精確重復(fù)查找算法的設(shè)計(jì)和實(shí)現(xiàn)過程,并以這些超短重復(fù)為種子,進(jìn)一步提出了啟發(fā)式的海明距離和編輯距離重復(fù)測(cè)定的數(shù)據(jù)并行化方法,并給出了可行的并行線程調(diào)度方案。并行重復(fù)查找算法設(shè)計(jì)過程中采用的按串行代碼功能區(qū)逐步完成并行化的方法,不但可以快速確定并行化過程中面臨的瓶頸問題,進(jìn)而判定整個(gè)算法的并行化難度,而且便于并行程序的設(shè)計(jì)、調(diào)試、分析和優(yōu)化,可以作為現(xiàn)存大多數(shù)串行算法實(shí)現(xiàn)并行化處理的參考。 第四,針對(duì)后綴數(shù)組構(gòu)造問題,提出了一種新的以排序方法替代傳統(tǒng)分組策略的并行后綴數(shù)組倍增構(gòu)造算法,其數(shù)據(jù)并行執(zhí)行效率明顯高于同類串行算法。后綴數(shù)組廣泛應(yīng)用于序列分析、字符串匹配和文本壓縮等領(lǐng)域,近年來,有關(guān)后綴數(shù)組構(gòu)造和應(yīng)用算法的不斷探索構(gòu)成了計(jì)算機(jī)科學(xué)中一個(gè)非�；钴S的研究領(lǐng)域。在對(duì)現(xiàn)有串行算法進(jìn)行了全面的分析和對(duì)比之后,通過抽象和等效替換的方法提出了一種適合于GPU計(jì)算的且更為簡(jiǎn)潔的并行后綴數(shù)組倍增構(gòu)造算法,不但能獨(dú)立完成后綴數(shù)組的并行構(gòu)造,還可與現(xiàn)存的串行倍增算法結(jié)合使用,以達(dá)到更高的執(zhí)行效率(速度可以達(dá)到同類串行算法3倍以上)。實(shí)驗(yàn)結(jié)果表明該算法在解決實(shí)際應(yīng)用問題時(shí),具有易于實(shí)現(xiàn)、執(zhí)行速度快和可擴(kuò)展性強(qiáng)等優(yōu)點(diǎn),是目前最快的單機(jī)運(yùn)行算法之一。尤其是在處理小字符集的生物序列數(shù)據(jù)時(shí),快于目前所有的串行算法。
【學(xué)位單位】：東北大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位年份】：2011
【中圖分類】：Q811.4;TP338.6
【部分圖文】：

東北大學(xué)博士學(xué)位論文 第1章緒論1.1研究背景與動(dòng)機(jī)自從1980年，英國(guó)和美國(guó)的生物化學(xué)家Frederick Sanger與Walter Gilbert發(fā)明DNA測(cè)序技術(shù)，DNA測(cè)序技術(shù)的發(fā)展取得了長(zhǎng)足的進(jìn)步，同時(shí)也產(chǎn)生了大量的序列數(shù)據(jù)。特別是2005年高通量并行測(cè)序技術(shù)逐漸成熟以來，不但測(cè)序的速度得到了近百倍的提升，而且測(cè)序的成本也下降了幾個(gè)數(shù)量級(jí)，目前每兆序列的成本低至1美元。同時(shí)，人們驚奇的發(fā)現(xiàn)在半導(dǎo)體技術(shù)領(lǐng)域?yàn)槿藗兯熘柖赏瑯舆m用于基因組測(cè)序領(lǐng)域，如圖1.1所示的Genbank數(shù)據(jù)庫(kù)中歷年存儲(chǔ)的序列數(shù)量新一代DNA測(cè)序技術(shù)操作更便捷，費(fèi)用更低廉，這些特點(diǎn)推動(dòng)了測(cè)序技術(shù)由大型測(cè)序中心向廣大研究單位和醫(yī)療機(jī)構(gòu)的普及。今后，各種測(cè)序技術(shù)可能成為一項(xiàng)廣泛使用的常規(guī)實(shí)驗(yàn)檢測(cè)手段，甚至個(gè)人基因組時(shí)代已為期不遠(yuǎn)，這將給生物學(xué)和醫(yī)學(xué)等領(lǐng)域帶來革命性的變革[16，17，37，38]。

(Power wall)、內(nèi)存墻（Memory wall)和指令級(jí)并行度 ILP 墻（Instruction-LevelParallelism)的限制，近年來已呈現(xiàn)明顯放緩的趨勢(shì)，如圖1.2所示_。自2002年到2006年，五年的時(shí)間單核處理器的性能只增加了的一倍，遠(yuǎn)遠(yuǎn)低于摩爾定-2-

圖2.1 CPU和GPU的fy:秒浮點(diǎn)運(yùn)算次數(shù)和存儲(chǔ)器帶寬Fig 2.1 Floating-point operations per second and memory bandwidth of CPU and GPU綜上所述，結(jié)合生物序列數(shù)據(jù)的特點(diǎn)，本文采用基于圖形處理器GPU的新
【參考文獻(xiàn)】

相關(guān)期刊論文 前2條

1 孫偉東;夏秀峰;馬宗民;;利用數(shù)據(jù)庫(kù)實(shí)現(xiàn)分布式任務(wù)的程序和數(shù)據(jù)存儲(chǔ)[J];航空電子技術(shù);2009年01期

2 孫偉東;王微微;馬宗民;;噬菌體基因文庫(kù)控制元件測(cè)定的并行處理方法[J];沈陽(yáng)航空工業(yè)學(xué)院學(xué)報(bào);2010年05期

本文編號(hào)：2854682