Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77821
Title: | 次世代序列比對的分析與加速 Analysis and Acceleration of Next Generation Sequence Alignment |
Authors: | Chan-Hsiang Lin 林展翔 |
Advisor: | 陳少傑 |
Keyword: | 生物資訊,基因定序,序列比對,BWA序列比對器,硬體加速, Bioinformatics,DNA Sequencing,DNA Alignment,Burrow-Wheeler Aligner,Hardware Acceleration, |
Publication Year : | 2018 |
Degree: | 碩士 |
Abstract: | 本篇論文提出一套針對生物基因定序(DNA Sequencing)應用軟體BWA(Burrows-Wheeler Aligner)的硬體加速電路設計。過去十年以來,生物資訊領域因為次世代定序技術發展十分迅速,在研究和應用方面都有相當大的突破。為了處理次世代定序產出的巨量資料,許多協助序列分析的軟體也應運而生,而BWA即為其中被廣泛使用的序列比對軟體之一。在本論文中我們首先針對BWA軟體進行演算法與效能分析,並且以硬體描述語言(Verilog HDL)對當中的Seed Generation流程進行重新設計,包含調整流程中的演算法和使用平行化的硬體架構達到加速目的,實作出可與異質運算平台相容的加速系統。目前已用軟體模擬驗證結果正確性,並估算約有2.6倍的速度提升。 This work presents the design of a hardware accelerated DNA sequence aligner that optimizes the widely used alignment tool, BWA-MEM, in the sequencing pipeline. Over the last decade, the progress of research and development in bioinformatics had a huge breakthrough owing to the tremendous improvement in Next Generation Sequencing (NGS) technology, which produces massive amount of raw digital data from samples in parallel. Many software tools have hence been designed to assist DNA sequencing, and together they form an end-to-end processing pipeline that transform raw input data into analytical results. Some of those tools in particular, are more commonly used because of their exceptional performance or ease of use. Burrows-Wheeler Aligner (BWA) is one of them. However, the performance of BWA still has plenty of room for improvement. By software analysis, we discover memory usage is the main hindrance for faster alignment and devised a hardware architecture on a heterogeneous platform that accelerates the seed generation process in BWA. Our design has been realized using Verilog HDL language and can be ported on a FPGA platform. The functional correctness of the accelerator has been verified by simulation, and its estimated overall performance is a 2.6x speedup, which is the fastest among other hardware implementations of the BWA algorithm that focus on optimizing the seed generation process. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/77821 |
DOI: | 10.6342/NTU201800744 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 電子工程學研究所 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-107-R04943031-1.pdf Restricted Access | 2.61 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.