由於生物科技的快速發展，DNA定序所需花費的時間不斷縮短以及各種基因體相關研究的進行，越來越多的生物序列資料備建立在基因序列資料庫之中，現今的DNA序列資料庫已含有數百億對的數量，如何在這龐大的資料庫中快速的找出相對應的序列是非常重要的課題。
序列比對是生物序列資訊中最重要的研究工具，用來比較及分析序列間彼此的相似程度，但在比對的時候，因序列的長度都是非常長，所以分析過程也曠時費工，因此許多的比對演算法被研究出來提高比對效率。
本論文旨在以FPGA實現一套生物序列比對時常用的Smith-Waterman演算法，並且實際按照理論值進行驗證，為了能更提升比對時間，本篇論文搭配了心跳式陣列，以心跳式陣列的平行處理能力，將傳統演算法低效率的處理過程修改為較高效的處理

Due to the rapid development of biotechnology, the time required for DNA sequencing has been shortened and various gene-related research has been carried out. More and more biological sequence data have been prepared in the gene se-quence database. Today's DNA sequence database Has been the number of tens of billions of dollars, how in this huge database to quickly find out the corresponding sequence is a very important issue.
Sequence alignment is the most important research tool in biological se-quence information to compare and analyze the similarity between sequences, but at the time of comparison, the length of the sequence is very long, so the analysis process will waste amount of time,So many of the alignment algorithms are being studied to improve the efficiency of comparison.
This paper aims to achieve a set of biological sequence alignment using the Smith-Waterman algorithm in FPGA, and actually according to the theoretical value of the verification, in order to improve the comparison time, this paper will use systolic array, parallel processing power of the array, the traditional algorithm of inefficient processing process modified to more efficient processing

[1] Baluška, František, Dieter Volkmann, and Peter W. Barlow. "Cell bodies in a cage." Nature 428.6981 (2004): 371-371..
[2] Stryer, Lubert. "Biosynthesis of amino acids and heme." Biochemistry 3 (1988): 575-600.
[3] Boyer, Robert S., and J. Strother Moore. "A fast string searching algorithm." Communications of the ACM 20.10 (1977): 762-772.
[4] http://www.nobelprize.org/educational/physics/integrated_circuit/history/
[5] Chelikowsky, J. "Introduction: Silicon in all its Forms." Silicon. Springer Berlin Heidelberg, 2004. 1-22.
[6] Renovell, Michel, et al. "IS-FPGA: a new symmetric FPGA architecture with implicit scan." Test Conference, 2001. Proceedings. International. IEEE, 2001.
[7] Blelloch, Guy E., and Bruce M. Maggs. "Parallel algorithms." Algorithms and theory of computation handbook. Chapman & Hall/CRC, 2010.
[8] Kung, Hsiang-Tsung. "Why systolic architectures?." IEEE computer 15.1 (1982): 37-46.
[9] Ristad, Eric Sven, and Peter N. Yianilos. "Learning string-edit distance." IEEE Transactions on Pattern Analysis and Machine Intelligence 20.5 (1998): 522-532.
[10] Masek, William J., and Michael S. Paterson. "A faster algorithm computing string edit distances." Journal of Computer and System sciences 20.1 (1980): 18-31.
[11] Needleman, S. B. "Needleman-Wunsch algorithm for sequence similarity searches." J Mol Biol 48 (1970): 443-453.
[12] Thompson, Julie D., Toby Gibson, and Des G. Higgins. "Multiple sequence alignment using ClustalW and ClustalX." Current protocols in bioinformatics (2002): 2-3.
[13] Smith, Temple F., and Michael S. Waterman. "Identification of common molecular subsequences." Journal of molecular biology 147.1 (1981): 195-197.
[14] Donnelly, Peter, and Richard D. Friedman. "DNA database searches and the legal consumption of scientific evidence." Michigan Law Review 97.4 (1999): 931-984.
[15] Carter, John, et al. "Impulse: Building a smarter memory controller." High-Performance Computer Architecture, 1999. Proceedings. Fifth International Symposium On. IEEE, 1999.
[16] 張廣淵. 存儲子系統. (編) 張廣淵. 計算機組裝與維護教程
[17] Bellman, Richard. Dynamic programming. Courier Corporation, 2013.
[18] https://reference.digilentinc.com/_media/nexys4ddr:nexys4ddr_rm.pdf
[19] Ciletti, Michael D. Advanced digital design with the Verilog HDL. Vol. 1. Upper Saddle River: Prentice Hall, 2003.
[20] Gill, Arthur. "Introduction to the theory of finite-state machines." (1962).
[21] Moore, Edward F. "Gedanken-experiments on sequential machines." Automata studies 34 (1956): 129-153.
[22] Mealy, George H. "A method for synthesizing sequential circuits." Bell Labs Technical Journal 34.5 (1955): 1045-1079.
[23] Table, A. S. C. I. I. "Ascii table." (2007).
[24] Mano, M. Morris, Charles R. Kime, and Tom Martin. Logic and computer design fundamentals. Vol. 3. Prentice Hall, 2008.
[25] Coffman, Ken. Real world FPGA design with Verilog. Pearson Education, 1999.
[26] Ciletti, Michael D. Advanced digital design with the Verilog HDL. Vol. 1. Upper Saddle River: Prentice Hall, 2003.