隨著科技的進步，生物科技也蓬勃的發展，DNA測序(DNA sequencing或稱DNA定序)是指分析DNA片段的鹼基序列，由A、T、C、G組成的長字串，此字串為DNA序列，在快速的DNA測序方法的推動了在生物學和醫學方面的研究和發現，可見DNA序列知識已成為不可缺少的知識，如今更多的生物序列資料被建立在基因序列資料庫中，要怎麼在這資料庫中快速且有效的找出相對應的序列是更重要的。

DNA序列比對是生物資訊學的一項重要的過程，因此在比對時出現很多的演算法，以提高比對效率。Field Programmable Gate Arrays(FPGA)也已廣泛的應用在生物信息學上。

本文介紹Burrows-Wheeler Aligner在FPGA上的硬體實現，利用Burrows-Wheeler Transform演算法和FM-index完成設計，並驗證結果分析較長序列的模擬波型圖。

With the advancement of technology, biotechnology has also flourished. DNA sequencing refers to the analysis of the base sequence of a DNA fragment; a long string consisting of A, T, C, and G. The string is a DNA sequence.The effective DNA sequencing method has promoted the study and development in biology and medicine. It shows that DNA sequence knowledge has become an indispensable knowledge. More and more biological sequence data is built in the gene sequence database these days. It is more important to find out the corresponding sequence quickly and efficiently in this database. DNA sequence alignment is an important process of bioinformatics. So,in order to improve the efficiency of comparison during the time, using many algorithms. Field Programmable Gate Arrays (FPGA) have also been widely used in bioinformatics. This paper introduces the hardware implementation of Burrows-Wheeler Aligner on FPGA. The Burrows-Wheeler Transform algorithm and FM-index are used to complete the design, and the results are analyzed to analyze the longer-order analog waveforms.

[1]František Baluška,Dieter Volkmann&Peter W. Barlow, “Cell bodies in a cage.”Nature 428,371(2004).
[2]Wikipedia-DNA
https://en.wikipedia.org/wiki/DNA
[3]Gibbs AJ,Mclntyre. ‘‘The diagram, a method for comparing sequences.’’ European Journal of Biochemistry, 1970, 16(1): 1-11.
[4]Needleman S B, Wunsch C D. ‘‘A general method applicable to the search for similarities in the amino acid sequence of two proteins.’’ Journal of molecular biology, 48(3): 443-453, 1970.
[5]Lam T W, Sung W K, Tam S L, et al. ‘‘Compressed indexing and local alignment of DNA.’’ Bioinformatics, 2008, 24(6): 791-797.
[6]Matthew Ruffalo,Thomas LaFramboise,Mehmet Koyutürk.‘‘Comparative analysis of algorithms for next-generation sequencing read alignment.’’
[7]Farzana Rahman, Mehedi Hassan, Alona Kryshchenko, Inna Dubchak, Tatiana V. Tatarinova, Nickolai Alexandrov. ‘‘benchNGS : An approach to benchmark short reads alignment tools.’’2015.
[8]Juan Cao; Xing Zheng ; Lingling Sun ; Jie Jin. ‘‘The Development Status and Trend of NetFPGA.’’ IEEE,2015.
[9]Chao Wang, Haijie Fang, Shiming Lei, Lei Gomg, Aili Wang, Xi Li, Xuehai Zhou‘‘GenServ: Genome Sequencing Services on Scalable Energy Efficient Accelerators’’ IEEE International Conference on Web Services 2017.
[10]OpenStax,Biology. OpenStax CNX. “DNA Structure and Sequencing.”2016.
[11]Obenrader,S. ‘‘The Sanger method.’’ 2003.
[12]Michael L.Metzker, “Sequencing technologies-the next gneration.”Nature Reviews Genetics11,31-46(2010).
[13]Loewe,L.“Genetics.Mutation.”Nature Education,2008, 1(1):113.
[14]Wikipedia- Integrated circuit
https://en.wikipedia.org/wiki/Integrated_circuit
[15]StephenM.Trimberger;JasonJ.Moore.‘‘FPGASecurity:Motivations,Features, and Applications.” Proceedings of the IEEE,2014.
[16]Wikipedia- Sequence alignment
https://en.wikipedia.org/wiki/Sequence_alignment
[17]Darja Kanduc, “Homeology, similarity, and identity in peptide epitope immunodefinition.” Journal of Peptide Science voiume 18, Issue 8 2012:487-494.
[18]Eric Sven Ristad,, and Peter N. Yianilos, “Learning String-Edit Distance.” IEEE Transactions on Pattern Analysis and Machine Intelligence, VOL.20, NO.5:522-532,1998.
[19]Stefan Canzar, Steven L. Salzberg, “Short Read Mapping:An Algorithmic Tour.” Proceedings of the IEEE(Volum:105, lssue:3, March 2017):436-458.
[20]Wikipedia-Suffix array.
https://en.wikipedia.org/wiki/Suffix_array
[21]Michael Burrows, David Wheeler. ‘‘A Block-Sorting Lossless Data Compression Algorithm.’’ DIGITAL SRC RESEARCH REPORT,1994.
[22]Heng Li, Richard Durbin. ‘‘Fast and accurate short reaad alignment with Burrows-Wheeler transform.’’Bioinformatics,Vol.25 no.14 2009.
[23]Vivado design suite-hlx editions, (online)Available:
https://www.xilinx.com/products/design-tools/vivado.html
[24]Wikipedia-米利型有限狀態機.
https://zh.wikipedia.org/wiki/%E7%B1%B3%E5%88%A9%E5%9E%8B%E6%9C%89%E9%99%90%E7%8A%B6%E6%80%81%E6%9C%BA
[25]Table, A.S.C.I.I. ‘‘Ascii table.’’2007.