Research Of Smith-Waterman Algorithm For Gene Sequencing And Its Implementation In FPGA

Gene sequencing is an important fundamental problem in the field of bioinformatics.It is mainly to obtain information in gene sequences.The fundamental method for gene sequencing is gene sequence alignment.At present,gene sequence alignment plays a very important role in clinical medicine.Analyzing human genetic information can provide doctors with a great reference when they are diagnosing and treating patients,and it can also help people prevent diseases.With the rapid development of modern instruments and sequencing technologies,the cost of gene sequencing has been greatly reduced,and the number of bases in gene databases has increased significantly.The number of bases that need to be analyzed for gene sequence comparison has greatly increased.However,the calculation speed of the existing computing resources and sequence comparison algorithms has been difficult to match the increase in the number of gene sequencing data,which is resulting in speed mismatch.In view of this problem,this paper proposes the research and implementation of the Smith-Waterman algorithm based on CPU-FPGA.This design analyzes the calculation principle of the Smith-Waterman algorithm.According to the algorithm in the process of calculating the score of the base sequence,combined with the characteristics of independent data on the diagonal line and the idea of dynamic programming,a parallel loop calculation scheme was proposed in the sequence scoring part.In the traceback part,two BRAM arrays are used,so that saving the traceback path and traceback can be performed simultaneously.In this paper,based on a CPU + FPGA heterogeneous platform,the hardware acceleration of the algorithm is implemented,using the Open CL standard,and the speed mismatch problem of sequence alignment is solved.In the process of realizing the entire system,the test data is transmitted to the DDR in the FPGA through PCIe,and then transmitted to the algorithm's FIFO for storage via the AXI bus,and the data is read according to the instructions for calculation.The algorithm includes a data writing module,a control module,a data temporary storage module,a data transmission module,an initial value module,a PE array module,a fractional temporary comparisonmodule,a backtracking module,and a data output module.In the SDAccel development environment of Xilinx,the control part of the system is completed using C language,implement then simulate the algorithm module with verilog language.The sequence comparison score part of the algorithm was developed using matlab language to verify the correctness of the hardware simulation results of the sequence comparison score.After the completion of the hardware simulation,a bitstream file is generated and configured into the FPGA to complete the operation.The experimental results show that the design successfully implements the hardware acceleration of the Smith-Waterman algorithm on a heterogeneous hardware platform of CPU+ FPGA,and obtain the correct optimal local sequence pair and the corresponding maximum score.The realized speed is 302.6 GCUPS,and Compared with other schemes that implement the algorithm,this design improves the operation speed of the algorithm.