請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78792
標題: | 具備仿射間隙評分法回溯功能之序列映射器平行架構設計 A Parallel Design of Dynamic Programming Sequence Aligner with Affine Gap Traceback |
作者: | Mao-Jan Lin 林茂然 |
指導教授: | 盧奕璋(Yi-Chang Lu) |
關鍵字: | 動態規劃序列映射器,回溯,硬體設計, dynamic programming,sequence aligner,traceback,hardware, |
出版年 : | 2019 |
學位: | 碩士 |
摘要: | 序列排序(sequence alignment)是生物資訊學中一個非常重要的問題,而基於動態規劃的序列映射器可以保證其排序結果為數學上的最佳解,因此有其應用上的不可取代性。然而動態規劃的時間複雜度使相關演算法在面對大量生物資訊時會耗費相當多的時間。過去有許多研究針對動態規劃設計硬體平行加速映射器,但由於記憶體上的限制,通常只提供排序最高分的結果,較少研究強調映射器的回溯(traceback)功能。
本論文提出一專用積體電路(Application-Specific Integrated Circuits, ASIC)設計之硬體加速器,此設計具備仿射間隙評分法(Affine Gap Penalty)的回溯功能。本論文提出兩個方向可以減少序列回溯時的記憶體使用量,並能幫助映射器更好的管線化(pipeline)時序。 本加速器使用台積電40奈米製程實作一個能夠排序兩條最長1024 x 992序列的動態規劃映射器,映射器可以輸入使用不同的蛋白質計分表。電路運作頻率為357 MHz,晶片大小$6.879 mm^2$,功率438.5 mW。在硬體模擬實驗中,我們使用硬體映射器加速MAFFT G-INS-1演算法中最耗費時間的配對排序(pairwise alignment)步驟,包含動態規劃與回溯所花費的時間比起軟體約加速570倍。 Sequence alignment plays an important role in bioinformatics. Since the alignment algorithms based on dynamic programming (DP) guarantee the optimal alignment results corresponding to the scoring system used, DP alignment algorithms have been popular since their invention. However, due to the time complexity of DP, the related algorithms consume a lot of time with rapidly increasing sizes of bioinformatics data. The situation induced many hardware parallelization design on DP aligner. However, due to the memory size limitation, few researches focus on the traceback function of DP sequence alignment algorithms. In this thesis, we propose an application-specific integrated circuits (ASIC) design on DP protein sequence aligner with affine gap traceback function. The author proposes two methods that can reduce the memory usage of traceback function and improve the pipeline timing of the design. The hardware is implemented with TSMC 40 nm technology. The maximum input sequence size of the aligner is $1024 imes 992$. The aligner can take different scoring table according to the input. The circuit operates at $357 MHz$, sized $6.879 mm^2$ with power $438.5 mW$. In post-layout simulation, we test our aligner design on the pairwise alignment step of G-INS-1 algorithm in MAFFT. The whole process including sequence alignment and traceback can be accelerated more than $570$ times comparing to software. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/78792 |
DOI: | 10.6342/NTU201900954 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-R05943039-1.pdf 目前未授權公開取用 | 7.94 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。