近年來，基因演算法對人體與疾病的研究來說是非常重要的領域。利用人體的基因序列與基因庫的資料進行比對，找出變異點的位置並且分析基因變異的問題。
而相比於在原有的方法利用CPU去執行，利用Field Programmable Gate Array (FPGA)去加速基因比對演算法已經是近年來很重要的趨勢，現代的演算法大多都透過展開或種子的方式去進行。本文所使用的基因比對演算法為BWA，並且利用SMEM找出最佳比對結果。
本文中利用FPGA去實現Burrows-Wheeler Aligner(BWA)的種子方法並且搭配FM-Index進行Backward Search演算法，以及搭配FMD-Index所進行的SMEM Seeding演算法，目的都在找出符合序列最佳比對解的方法。這個方法藉由存取所需要的資料，計算出在演算法的過程中所需要的運算值，並且進行比對的迭代運算。此方法不但能夠節省因比對過程中所產生的記憶體占用量，更可以節省資料的存取時間以加速基因比對的過程。
本研究使用Xilinx Virtex-7 NetFPGA-SUME開發板進行開發，並且提出了四大模組以及系統架構包括控制模組、解碼模組、資料要求模組、資料接收模組、比對模組、PCIE控制器以及MIG記憶體控制器，並且利用AXI匯流排去進行交換。
本文的研究方法與CPU執行SMEM Seeding的效能進行比較，我們將此基因序列比對演算法的效能提高了14.7倍。我們也將進一步去分析研究中所遇到的各種設計瓶頸與困難以及值得改善的方法與方向，並且在有效的硬體中如何達到最大效能。

In recent years, gene sequence alignment algorithm is a very important field for the research of human body and disease. The gene sequence can be compared with the data of the gene database to find the location of mutation and analyze the problem of gene mutation.
Compared with the original method using the CPU to execute gene sequence alignment, the use of FPGA to accelerate the gene sequence alignment algorithm has been a very important trend in recent years. Most algorithms are carried out by means of unfolding or seeding. The gene alignment algorithm used in this research is BWA, and SMEM is used to find the best alignment result.
In the research, FPGA is used to implement the seed method of BWA and used with FM Index for Backward Search algorithm, and with FMD-Index for SMEM Seeding algorithm. The purpose is to find out the method of the best alignment solution in accordance with the sequence. This method calculates the iterative operation value needed in the algorithm process by accessing the required data, and performs the iterative operation of alignment. The method can not only save the memory occupied by the alignment process, but also save the time of data access to speed up the process of gene alignment.
Xilinx Virtex-7 NetFPGA-SUME development board was used to develop in this research, and four major modules and the system architecture are proposed including control module, decoding module, data request module, data receiving module, alignment module, PCIE controller and MIG memory controller, and use AXI bus to exchange data.
From the alignment between the method in our research and the performance of CPU execution SMEM Seeding, we have increased the performance of the genetic alignment algorithm by 14.7 times. We will also further analyze the various design bottlenecks and difficulties encountered in the research, as well as methods of improvement, and achieving maximum performance in effective hardware.

[1] M. L. Metzker, “Sequencing technologiesthe next generation,”Nature reviews genetics, vol. 11, no. 1, p. 31, 2010.
[2] T. F. Smith, M. S. Waterman et al., “Identification of common molecular subsequences,” Journal of molecular biology, vol.147, no. 1, pp. 195–197, 1981.
[3] S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” Journal of molecular biology, vol. 48, no. 3, pp. 443–453, 1970.
[4] N. Homer, B. Merriman, and S. F. Nelson, “Bfast: an alignment tool for large scale genome resequencing,” PloS one, vol. 4, no. 11, p. e7767, 2009.
[5] S. F. Altschul, T. L. Madden, A. A. Sch¨affer, J. Zhang, Z. Zhang, W. Miller, and D. J. Lipman, “Gapped blast and psiblast: a new generation of protein database search programs,”Nucleicacids research, vol. 25, no. 17, pp. 3389–3402, 1997.
[6] S. Salamat and T. Rosing, “FPGA Acceleration of Sequence Alignment:A Survey,” arXiv preprint arXiv:2002.02394v2, 2020.
[7] I. H. G. S. Consortium et al., “Initial sequencing and analysis of the human genome,” nature, vol. 409, no. 6822, p.860, 2001.
[8] Y. Turakhia, G. Bejerano, and W. J. Dally, “Darwin: A genomics co-processor provides up to 15,000 x acceleration on long read assembly,” in ACM SIGPLAN Notices, vol. 53, no. 2. ACM,2018, pp.199–213.
[9] E. D. Pleasance, R. K. Cheetham, P. J. Stephens, D. J. McBride,S. J. Humphray, C. D. Greenman, I. Varela, M.-L. Lin, G. R.Ordo ́nez, G. R. Bignell ̃ et al., “A comprehensive catalogue of somatic mutations from a human cancer genome,” Nature, vol.463, no. 7278, p. 191, 2010.
[10] LACOUR, A., et al. Genome-wide significant risk factors for Alzheimer’s disease: role in progression to dementia due to Alzheimer's disease among subjects with mild cognitive impairment. Molecular psychiatry, 2017, 22.1: 153-160.
[11] Y. Cho, C.-H. Lee, E.-G. Jeong, M.-H. Kim, J. H. Hong, Y. Ko, B. Lee, G. Yun, B. J. Kim, J. Jung et al., “Prevalence of rare genetic variations and their implications in ngs-data interpretation,” Scientific reports, vol. 7, no. 1, p. 9810, 2017.
[12] N. Krumm, T. N. Turner, C. Baker, L. Vives, K. Mohajeri, K. Witherspoon, A. Raja, B. P. Coe, H. A. Stessman, Z.-X.He et al., “Excess of rare, inherited truncating mutations in autism,” Nature genetics, vol. 47, no. 6, p. 582, 2015.
[13] O. Spichenok, Z. M. Budimlija, A. A. Mitchell, A. Jenny, L. Kovacevic, D. Marjanovic, T. Caragine, M. Prinz, and E. Wurmbach, “Prediction of eye and skin color in diverse populations using seven snps,” Forensic Science International: Genetics, vol. 5, no. 5, pp. 472–478, 2011.
[14] T. C. Sequencing, R. H. Waterson, E. S. Lander, R. K. Wilson, A. Consortium et al., “Initial sequence of the chimpanzee genome and comparison with the human genome,” Nature, vol. 437, no. 7055, p. 69, 2005.
[15] C. Y. McLean, P. L. Reno, A. A. Pollen, A. I. Bassan, T. D. Capellini, C. Guenther, V. B. Indjeian, X. Lim, D. B. Menke, B. T. Schaar et al., “Human-specific loss of regulatory dna and the evolution of human-specific traits,” Nature, vol. 471, no. 7337, p. 216, 2011.
[16] M. A. Hamburg and F. S. Collins, “The path to personalized medicine,” New England Journal of Medicine, vol. 363, no. 4, pp. 301–304, 2010.
[17] A. Al Kawam, S. Khatri, and A. Datta, “A survey of software and hardware approaches to performing read alignment in next generation sequencing,” IEEE/ACM transactions on computational biology and bioinformatics, vol. 14, no. 6, pp. 1202–1213, 2016.
[18] Heng Li and Richard Durbin. Fast and accurate short read alignment with burrows{wheeler transform. Bioinformatics, 25(14):1754{1760, 2009.
[19] S. Kumar, K. K. Krishnani, B. Bhushan, and M. P. Brahmane,“Metagenomics: retrospect and prospects in high throughput age,” Biotechnology research international, vol. 2015, 2015.
[20] D. Fujiki, A. Subramaniyan, T. Zhang, Y. Zeng, R. Das, D. Blaauw, and S. Narayanasamy, “Genax: a genome sequencing accelerator,” in Proceedings of the 45th Annual International Symposium on Computer Architecture. IEEE Press, 2018, pp. 69–82.
[21] E. E. Schadt, S. Turner, and A. Kasarskis, “A window into third-generation sequencing,” Human molecular genetics, vol. 19, no. R2, pp. R227–R240, 2010.
[22] D. Gordon, J. Huddleston, M. J. Chaisson, C. M. Hill, Z. N. Kronenberg, K. M. Munson, M. Malig, A. Raja, I. Fiddes, L. W. Hillier et al., “Long-read sequence assembly of the gorilla genome,” Science, vol. 352, no. 6281, p. aae0344, 2016.
[23] S. Goodwin, J. Gurtowski, S. Ethe-Sayers, P. Deshpande, M. C. Schatz, and W. R. McCombie, “Oxford nanopore sequencing, hybrid error correction, and de novo assembly of a eukaryotic genome,” Genome research, vol. 25, no. 11, pp. 1750–1756, 2015.
[24] CHUN, Jongsik, et al. EzTaxon: a web-based tool for the identification of prokaryotes based on 16S ribosomal RNA gene sequences. International journal of systematic and evolutionary microbiology, 2007, 57.10: 2259-2261.
[25] Z. Ning, A. J. Cox, and J. C. Mullikin, “Ssaha: a fast search method for large dna databases,” Genome research, vol. 11, no. 10, pp. 1725–1729, 2001.
[26] Ben Langmead, Cole Trapnell, Mihai Pop, Steven L Salzberg, et al. Ultrafast and memory-ecient alignment of short dna sequences to the human genome.Genome biol, 10(3):R25, 2009.
[27] Ruiqiang Li, Chang Yu, Yingrui Li, Tak-Wah Lam, Siu-Ming Yiu, Karsten Kristiansen, and Jun Wang. Soap2: an improved ultrafast tool for short read alignment. Bioinformatics, 25(15):1966{1967, 2009.
[28] BURROWS, Michael; WHEELER, David. A block-sorting lossless data compression algorithm. In: Digital SRC Research Report. 1994.
[29] P. Ferragina and G. Manzini, “Opportunistic data structures with applications,” in Proceedings 41st Annual Symposium on Foundations of Computer Science. IEEE, 2000, pp. 390–398.
[30] P. Ferragina and G. Manzini (2000). Opportunistic Data Structures with Applications. In Proceedings of FOCS, pages 390 – 398.
[31] H. Li. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arXiv preprint arXiv:1303.3997, 2013.
[32] XILINX, I. series FPGAs configurable logic block: user guide. San Jose, CA: Xilinx, 2014.
[33] AMBA, AXI; SPECIFICATION, ACE Protocol. ARM. Cambridge, UK, 2011.
[34] Vivado Design Suite Vivado AXI Referenc UG1037 (v4.0) July 15, 2017
[35] H. Li, “Exploring single-sample SNP and INDEL calling with whole- genome De Novo assembly,” Bioinformatics, vol. 28, no. 14, pp. 1838– 1844, Jul. 2012.
[36] LI, Heng; DURBIN, Richard. Fast and accurate short read alignment with Burrows–Wheeler transform. bioinformatics, 2009, 25.14: 1754-1760.
[37] AHMED, Nauman, et al. Heterogeneous hardware/software acceleration of the BWA-MEM DNA alignment algorithm. In: 2015 IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE, 2015. p. 240-246.
[38] QADER, Dana Abdul. A High Performance Architecture for an Exact Match Short-Read Aligner Using Burrows-Wheeler Aligner on FPGAs. 2015.
[39] AHMED, Nauman; BERTELS, Koen; AL-ARS, Zaid. A comparison of seed-and-extend techniques in modern DNA read alignment algorithms. In: 2016 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). IEEE, 2016. p. 1421-1428.
[40] HOUTGAST, Ernst Joachim, et al. GPU-accelerated BWA-MEM genomic mapping algorithm using adaptive load balancing. In: International conference on architecture of computing systems. Springer, Cham, 2016. p. 130-142.
[41] CHANG, Mau-Chung Frank, et al. The smem seeding acceleration for dna sequence alignment. In: 2016 IEEE 24th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM). IEEE, 2016. p. 32-39.
[42] VASIMUDDIN, Md, et al. Efficient architecture-aware acceleration of BWA-MEM for multicore systems. In: 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, 2019. p. 314-324.
[43] SUBRAMANIYAN, Arun, et al. Accelerating maximal-exact-match seeding with enumerated radix trees. BioRxiv, 2020.
[44] CHEN, Nae-Chyun; LI, Yu-Cheng; LU, Yi-Chang. A memory-efficient fm-index constructor for next-generation sequencing applications on fpgas. arXiv preprint arXiv:2102.03045, 2021.
[45] CONG, Jason, et al. SMEM++: a pipelined and time-multiplexed SMEM seeding accelerator for genome sequencing. In: 2018 28th International Conference on Field Programmable Logic and Applications (FPL). IEEE, 2018. p. 210-2104.
[46] REDDY, M. SivaPrasad; RAJESH, B. Babu; PRASAD, Tvs Gowtham. A Synthesizable Design of AMBA-AXI Protocol for SoC Integration. International Journal of Engineering Inventions, 1.3: 19-26.
[47] DEEPU, M. Prasanna; DHANABAL, R. Validation of transactions in AXI protocol using system verilog. In: 2017 International conference on Microelectronic Devices, Circuits and Systems (ICMDCS). IEEE, 2017. p. 1-4.
[48] SUNDARARAJAN, Prasanna. High performance computing using FPGAs. Technical Report. Available Online 2010: www. xilinx. com/support/documentation/white papers/wp 375 HPC Using FPGAs. pdf, 2010.
[49] TUAN, Tim; LAI, Bocheng. Leakage power analysis of a 90nm FPGA. In: Proceedings of the IEEE 2003 Custom Integrated Circuits Conference, 2003. IEEE, 2003. p. 57-60.
[50] NEUGEBAUER, Rolf, et al. Understanding PCIe performance for end host networking. In: Proceedings of the 2018 Conference of the ACM Special Interest Group on Data Communication. 2018. p. 327-341.
[51] GONG, Jian, et al. An efficient and flexible host-FPGA PCIe communication library. In: 2014 24th international conference on field programmable logic and applications (FPL). IEEE, 2014. p. 1-6.
[52] LI, Heng. Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly. Bioinformatics, 2012, 28.14: 1838-1844.