基因測序是生物信息學(xué)領(lǐng)域中重要的基礎(chǔ)性問題,主要是獲取基因序列中的信息,進(jìn)行基因測序的根本方法是基因序列比對(duì)。目前,基因序列比對(duì)在臨床醫(yī)學(xué)上有著十分重要的作用,分析人類基因信息,可為醫(yī)生在診斷,治療病人時(shí),提供極大的參考,也可以為人們預(yù)防疾病提供幫助。隨著新一代測序儀器與測序技術(shù)的快速發(fā)展,基因測序的成本大大降低,基因數(shù)據(jù)庫中的堿基數(shù)量大幅度增加。進(jìn)行基因序列比對(duì)需要分析的堿基數(shù)量出現(xiàn)了極大的增長,而現(xiàn)有的計(jì)算資源與序列比對(duì)算法的計(jì)算速度,已經(jīng)難以匹配目前基因測序數(shù)據(jù)數(shù)量的增長速度,導(dǎo)致出現(xiàn)速度失配問題。針對(duì)這一問題,本文提出了一種基于CPU-FPGA的Smith-Waterman算法的硬件加速方案。本設(shè)計(jì)對(duì)Smith-Waterman算法的計(jì)算原理進(jìn)行分析,根據(jù)該算法在堿基序列計(jì)算得分的過程中,反對(duì)角線上的數(shù)據(jù)互不依賴的特征,結(jié)合動(dòng)態(tài)規(guī)劃思想,在序列打分部分提出了并行循環(huán)計(jì)算方案。在回溯部分,使用兩個(gè)BRAM陣列,使保存回溯路徑和回溯可同時(shí)進(jìn)行。本文基于CPU+FPGA的異構(gòu)平臺(tái),采用Open CL標(biāo)準(zhǔn),實(shí)現(xiàn)該算法的硬件加速,解決了序列比對(duì)的速度失配問題。在實(shí)現(xiàn)整個(gè)系統(tǒng)的過程中,通過... 

【文章來源】：深圳大學(xué)廣東省

【文章頁數(shù)】：67 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

異構(gòu)平臺(tái)系統(tǒng)設(shè)計(jì)圖

型或算法，在兩個(gè)或多個(gè)序列之間找出最優(yōu)匹配的堿基序列，比對(duì)的結(jié)果反映了已知序列和目的序列之間相似性的程度以及它們的生物學(xué)特征。序列比對(duì)是生物信息計(jì)算中的核心，也是生物學(xué)中最基本、最重要的一個(gè)方法。按照同時(shí)參與比對(duì)的序列條數(shù)，分為多序列比對(duì)和雙序列比對(duì)；從進(jìn)行比對(duì)的序列范圍考慮，分為全局序列比對(duì)和局部序列比對(duì)[26]。一般研究的序列比對(duì)多為雙序列比對(duì)，雙序列比對(duì)的研究是多序列比對(duì)的基矗參與序列比對(duì)的兩條序列分別參考序列與目的序列。在全局范圍內(nèi)將兩條序列進(jìn)行比對(duì)打分的方法稱為全局序列比對(duì)，如圖2-1，適用于非常相似且長度也大致相等的序列；局部比對(duì)序列是一種匹配子序列的序列比對(duì)方法，如圖2-2，適用于某些片段相似的序列。圖2-1全局序列比對(duì)示意圖圖2-2局部序列比對(duì)示意圖假設(shè)進(jìn)行序列比對(duì)的參考序列是S=s1s2s3...si,目的序列是T=t1t2t3...tj,其中i,j分別表示參考序列與目的序列的長度。當(dāng)參考序列S與目的序列T進(jìn)行比對(duì)，將會(huì)出現(xiàn)以下三種情況，分別是：1）插入：目的序列T與參考序列S相比插入了新的序列，參考序列S出現(xiàn)空位。2）刪除：目的序列T與參考序列S相比刪除了舊的序列，目的序列T出現(xiàn)空位。

嗨菩緣某潭紉約八??的生物學(xué)特征。序列比對(duì)是生物信息計(jì)算中的核心，也是生物學(xué)中最基本、最重要的一個(gè)方法。按照同時(shí)參與比對(duì)的序列條數(shù)，分為多序列比對(duì)和雙序列比對(duì)；從進(jìn)行比對(duì)的序列范圍考慮，分為全局序列比對(duì)和局部序列比對(duì)[26]。一般研究的序列比對(duì)多為雙序列比對(duì)，雙序列比對(duì)的研究是多序列比對(duì)的基矗參與序列比對(duì)的兩條序列分別參考序列與目的序列。在全局范圍內(nèi)將兩條序列進(jìn)行比對(duì)打分的方法稱為全局序列比對(duì)，如圖2-1，適用于非常相似且長度也大致相等的序列；局部比對(duì)序列是一種匹配子序列的序列比對(duì)方法，如圖2-2，適用于某些片段相似的序列。圖2-1全局序列比對(duì)示意圖圖2-2局部序列比對(duì)示意圖假設(shè)進(jìn)行序列比對(duì)的參考序列是S=s1s2s3...si,目的序列是T=t1t2t3...tj,其中i,j分別表示參考序列與目的序列的長度。當(dāng)參考序列S與目的序列T進(jìn)行比對(duì)，將會(huì)出現(xiàn)以下三種情況，分別是：1）插入：目的序列T與參考序列S相比插入了新的序列，參考序列S出現(xiàn)空位。2）刪除：目的序列T與參考序列S相比刪除了舊的序列，目的序列T出現(xiàn)空位。

【參考文獻(xiàn)】：
期刊論文
[1]雙序列比對(duì)算法的研究與改進(jìn)[J]. 李丹.  電子技術(shù)與軟件工程. 2017(18)
[2]基因測序、基因治療與精準(zhǔn)醫(yī)療[J]. 祁鳴,蔡澤泓.  科學(xué)24小時(shí). 2016(11)
[3]基于多核流處理器的BLAST并行化算法研究[J]. 裴頌文,王心怡,韋剛,吳百鋒.  系統(tǒng)仿真學(xué)報(bào). 2011(10)
[4]基于SSE2的Smith-Waterman算法并行優(yōu)化[J]. 王艷.  赤峰學(xué)院學(xué)報(bào)(科學(xué)教育版). 2011(07)
[5]基于HPM模型的Smith-Waterman算法并行優(yōu)化[J]. 李玉崗,劉志勇.  計(jì)算機(jī)工程. 2007(01)
[6]生物信息學(xué)概述[J]. 尚彤,張丹,盧銘.  北京大學(xué)學(xué)報(bào)(醫(yī)學(xué)版). 2001(01)

碩士論文
[1]基于SOPC的Smith-Waterman算法硬件加速器的設(shè)計(jì)與實(shí)現(xiàn)[D]. 王剛.電子科技大學(xué) 2019
[2]雙序列比對(duì)Needleman-Wunsch算法研究[D]. 姜鮮桃.內(nèi)蒙古農(nóng)業(yè)大學(xué) 2017
[3]Smith-Waterman算法硬件加速的研究與實(shí)現(xiàn)[D]. 陳觀君.電子科技大學(xué) 2017
[4]基于GPU的BLAST程序的并行計(jì)算的研究[D]. 胡婭.浙江理工大學(xué) 2011



本文編號(hào)：3591087