Tiger基於字元基因序列比對硬體加速器

Abstract

本論文提出一個專門針對生物基因定序(DNA Sequencing)應用軟體TIGER (Tiled Iterative Genome Assembler and Approximate Multi-Genome Aligner)中的基因比對(Alignment)流程改良的硬體加速電路設計。有鑑於生物醫學的研究與發展、次世代定序(Next Generation Sequencing)技術的發明，使得基因定序技術在近年來已有相當大幅度地突破，現今的基因定序應用軟體以由UIUC 所發展的TIGER 基因體分析工具包較為著名，並在生物醫學領域被廣泛研究使用。然而這類軟體仍存在著許多先天上的不足之處，例如：執行效能受限於其軟體開發環境、部份功能的演算法效率不佳等，因此亟需以另一種方式實現TIGER以解決上述問題。 在本論文中我們會改善比對軟體的演算法並以軟體語言(C++)以及硬體描述語言(Verilog HDL)對TIGER中的基因序列比對流程進行重新設計：包含簡化流程中的演算法並降低運算複雜度、使用平行化的硬體架構達到加速目的；並在硬體描述語言上，透過 Field Programmable Gate Array (FPGA)驗證我們的設計。

This Thesis presents a hardware acceleration design which specifically aims to speed up the alignment flow in the Tiled Sequential Genome Assembler and Approximate Multi-Genome Aligner. In the research and development of biomedicine, the invention of Next Generation Sequencing technology has led to a considerable breakthrough in gene sequencing technology in recent years. Nowadays, the TIGER Genome Analysis Toolkit developed by UIUC is a well known and widely used sequencing application software. However, there are still many inherent deficiencies in this kind of software. For example, the execution performance is limited by its software development environment and the use of inefficient algorithms in some functions. Therefore, it is urgent to implement TIGER in a better way to solve the above problem. In this Thesis, we use software language (C ++) and hardware description language (Verilog HDL) to redesign the TIGER genome sequence alignment process. We improve the algorithm used in alignment process and reduce the complexity of its parallel hardware architecture such that we can achieve acceleration by programming hardware description language on a Field Programmable Gate Array (FPGA) board.