上個(gè)世紀(jì)末到21世紀(jì)初,隨著人類的基因組計(jì)劃和各類基因工程的深入實(shí)施,生物信息數(shù)據(jù)正以指數(shù)級的速度增加。這些生物信息將影響著藥學(xué)、醫(yī)學(xué)、農(nóng)業(yè)和環(huán)保等方面的研究與發(fā)展,還有助于人們提高生活質(zhì)量。其民用的一種主要技術(shù)是基因測序。基因測序作為一種新型基因檢測技術(shù),能夠從血液或唾液中提取基因全序列,對這些基因全序列進(jìn)行測定,從而分析出基因數(shù)據(jù)中攜帶疾病的可能性,進(jìn)而提出科學(xué)的指導(dǎo),以使其得到正確地治療。在應(yīng)用價(jià)值上,基因測序速度的加快,能夠更快地找出疾病,這樣能獲得充足的時(shí)間用于治療階段,最終提高癌癥治愈率和出生兒缺陷,可提高人類健康水平。通過分析各個(gè)序列比對的計(jì)算原理和速度,本文提出Myers算法作為基因測序中的全局序列比對算法,并在FPGA平臺上實(shí)現(xiàn)進(jìn)行加速,從而加速基因測序速度。通過對Myers算法中的PE模塊電路進(jìn)行分析,對關(guān)鍵電路進(jìn)行優(yōu)化,減少電路延時(shí),使得整個(gè)系統(tǒng)的時(shí)鐘頻率得以提升,用來提高系統(tǒng)的計(jì)算量。系統(tǒng)測試結(jié)果表明,本系統(tǒng)運(yùn)行于基于KCU1500實(shí)驗(yàn)平臺的時(shí)鐘頻率可以達(dá)到181MHz,且每秒可以處理7032萬對基因序列,為在CPU平臺上運(yùn)行速度的56倍。本文主要的研究內(nèi)容和完... 

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

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

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

【部分圖文】：

KCU1500實(shí)驗(yàn)平臺該實(shí)驗(yàn)平臺只需要插入帶有PCIe接口的電腦上即可使用，無需額外的電路輔助

基因序列比對Myers算法的FPGA實(shí)現(xiàn)33圖5-4C代碼隨機(jī)產(chǎn)生測試的數(shù)據(jù)圖5-4中的第一行數(shù)據(jù)是待檢測基因序列的結(jié)構(gòu)數(shù)據(jù)，所以第一個(gè)Byte的最高位是1。第二個(gè)Byte是表示待檢測基因序列的長度，接著的四個(gè)Byte是待檢測基因序列中文件的位置，按照順序增加。剩下的數(shù)據(jù)是待檢測基因序列，每兩位代表基因序列的一個(gè)堿基。第二行數(shù)據(jù)是候選基因序列的結(jié)構(gòu)數(shù)據(jù)，所以第一個(gè)Byte的最高位為0，ID號與待檢測基因序列的一樣，即0x01。第二個(gè)Byte是染色體編號，這不影響計(jì)算和驗(yàn)證結(jié)果，這里設(shè)定為固定值0x01。接著的四個(gè)Byte是基因庫的位置，這個(gè)信息也不會影響結(jié)果，所以用來計(jì)數(shù)每個(gè)待檢測基因序列的候選基因序列的個(gè)數(shù)。后面的基因序列為候選基因序列，與待檢測基因序列一樣，每兩位表示一個(gè)堿基，但其長度比待檢測基因序列的長度多兩個(gè)，這是為了防止基因進(jìn)行了突變，出現(xiàn)‘-’空位，而導(dǎo)致計(jì)算出來的結(jié)果會有差別。后面幾行的數(shù)據(jù)信息跟前面的信息一樣，只是運(yùn)算到下一個(gè)待檢測基因序列，ID號就會增加，用來標(biāo)志為不同的待檢測基因序列。從圖5-4中還可以得知，第1條待檢測基因序列有1條候選基因序列；第2條待檢測基因序列同樣有1條候選基因序列；第3條待檢測基因序列有4條候選基因序列；第4、5條待檢測基因序列都有6條候選基因序列。這可以得出PC端產(chǎn)生的數(shù)據(jù)具有隨機(jī)性。經(jīng)過Myers算法計(jì)算，PC端得出對應(yīng)序列比對的得分結(jié)果如圖5-5所示。

基因序列比對Myers算法的FPGA實(shí)現(xiàn)34圖5-5隨機(jī)產(chǎn)生數(shù)據(jù)的Myers算法結(jié)果從圖5-5中得知，由于這些數(shù)據(jù)是隨機(jī)產(chǎn)生的，因此相似度并不高，導(dǎo)致計(jì)算的結(jié)果得分值較高，而基因測序中兩條相似度較高的基因序列比對的得分會較低。在Vivado軟件上，使用PC端產(chǎn)生的數(shù)據(jù)，對Myers模塊進(jìn)行仿真，截取PEArray模塊仿真的結(jié)果如圖5-6所示。從圖中得出，雖然輸入的數(shù)據(jù)并沒有全部連續(xù)，即有些連續(xù)，有些不連續(xù)，但可以看到結(jié)果的輸出時(shí)序與數(shù)據(jù)的輸入時(shí)序一樣，即Val_o信號跟Val_i信號的波形一樣，相當(dāng)于數(shù)據(jù)進(jìn)行若干個(gè)時(shí)鐘計(jì)算后，計(jì)算的結(jié)果還是一個(gè)時(shí)鐘接著一個(gè)時(shí)鐘依次輸出的。圖5-6仿真結(jié)果輸入的數(shù)據(jù)不連續(xù)是因?yàn)樽x取到待檢測基因序列時(shí)，需要花費(fèi)一個(gè)時(shí)鐘周期，而此時(shí)因?yàn)闆]有對應(yīng)的候選基因序列，所以該時(shí)鐘周期沒有參與計(jì)算。但在基因測序中，由于一條待檢測基因序列至少有幾萬條候選基因序列，甚至高達(dá)幾十萬條基因序列，所以相對于幾萬個(gè)時(shí)鐘和幾十萬個(gè)時(shí)鐘來說，花費(fèi)的這個(gè)時(shí)鐘基本可以忽略。因此這個(gè)系統(tǒng)的計(jì)算等同于每個(gè)時(shí)鐘可以計(jì)算一對基因序列對，即計(jì)算出一條待檢測基因序列和一條候選基因序列的比對結(jié)果。為了驗(yàn)證數(shù)據(jù)的正確性，對仿真的得分結(jié)果進(jìn)行放大，如圖5-7所示。其中當(dāng)val_o信號為1時(shí)，此刻的輸出得分才有效，反之是一個(gè)隨機(jī)數(shù)，沒有實(shí)際意義。

【參考文獻(xiàn)】：
期刊論文
[1]基于FPGA實(shí)現(xiàn)快速矩陣求逆算法[J]. 張繁,何明亮.  通信技術(shù). 2020(02)
[2]基于高通量測序技術(shù)研究黃櫨根際土壤微生物多樣性[J]. 周江鴻,夏菲,車少臣,葛雨萱,周肖紅.  園林科技. 2019(03)
[3]基于高通量測序技術(shù)研究黃櫨根際土壤微生物多樣性[J]. 周江鴻,夏菲,車少臣,葛雨萱,周肖紅.  園林科技. 2019 (03)
[4]基于動(dòng)態(tài)規(guī)劃的雙序列比對算法構(gòu)件設(shè)計(jì)與實(shí)現(xiàn)[J]. 石海鶴,周衛(wèi)星.  計(jì)算機(jī)研究與發(fā)展. 2019(09)
[5]面向嵌入式FPGA的高性能卷積神經(jīng)網(wǎng)絡(luò)加速器設(shè)計(jì)[J]. 曾成龍,劉強(qiáng).  計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào). 2019(09)
[6]高通量基因測序技術(shù)在胎兒性染色體非整倍體檢測中的應(yīng)用[J]. 蔡海英,許華英,熊卿圓.  中國現(xiàn)代藥物應(yīng)用. 2019(15)
[7]產(chǎn)前篩查及無創(chuàng)基因測序技術(shù)在胎兒出生缺陷中的診斷效果及對妊娠結(jié)局的影響研究[J]. 王新玲,尹璐,段雅.  中國優(yōu)生與遺傳雜志. 2019(07)
[8]Smith-Waterman算法優(yōu)化改進(jìn)與Spark并行化研究[J]. 李雷孝,劉燕鳳,高靜.  內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版). 2019(05)
[9]高通量基因測序技術(shù)檢測外周血循環(huán)腫瘤DNA基因突變在非小細(xì)胞肺癌中的應(yīng)用[J]. 呂爽,李卉,巴雅力格,孫巖巖,呼群.  現(xiàn)代腫瘤醫(yī)學(xué). 2019(13)
[10]Needleman-Wunsch算法的改進(jìn)[J]. 張玉虎,周正.  火力與指揮控制. 2019(05)

博士論文
[1]生物信息學(xué)中多序列比對等算法的研究[D]. 張敏.大連理工大學(xué) 2005
[2]生物信息學(xué)中的序列比對算法研究[D]. 唐玉榮.中國農(nóng)業(yè)大學(xué) 2004

碩士論文
[1]高通量測序數(shù)據(jù)集的短讀序列比對算法研究[D]. 孫繼鵬.西安電子科技大學(xué) 2019
[2]基于SOPC的Smith-Waterman算法硬件加速器的設(shè)計(jì)與實(shí)現(xiàn)[D]. 王剛.電子科技大學(xué) 2019
[3]雙序列比對Needleman-Wunsch算法研究[D]. 姜鮮桃.內(nèi)蒙古農(nóng)業(yè)大學(xué) 2017
[4]Smith-Waterman算法硬件加速的研究與實(shí)現(xiàn)[D]. 陳觀君.電子科技大學(xué) 2017
[5]雙序列比對Needleman-Wunsch算法的分布式并行優(yōu)化研究[D]. 馮百龍.內(nèi)蒙古農(nóng)業(yè)大學(xué) 2015
[6]生物序列比較算法的研究[D]. 郭曉冬.杭州電子科技大學(xué) 2012



本文編號：3595207