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

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

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

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

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

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

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