Sequence alignment algorithms are the fundamental and indispensable tools for contemporary research in the field of bioinformatics. Smith Waterman algorithm is one of such algorithms that is capable of performing sequence alignment high in quality, but slow at speed. The purpose of this project is to design and develop the hardware accelerator for sequence alignment based upon the Smith-Waterman algorithm. The ultimate goal is to use rapid design methodology in order to implement the algorithm on a dedicated heterogeneous system (CPU+FPGA) to greatly improve the computational throughput. In addition, in order to make FPGA more accessible to non-expert computer users, a user-friendly front panel is designed with NI LabVIEW to alleviate the pain of programming and using the hardware accelerator.
Figure 1 represents the ConVI Flow, which is composed of Convey HC-1 hybrid core computer and NI LabVIEW FPGA. The amount of time used for implementing Smith Waterman algorithm can be significantly decreased by using LabVIEW, the graphical programming environment. With LabVIEW FPGA and additional features developed for specifically targeting Convey HC-1 hybrid core computer, the hardware design of Smith Waterman can be migrated to Convey HC-1 for accelerated data processing.
Fig. 1 ConVI structure
Under the hood, the ConVI Pipeline Wrapper allow users to configure the pipelines using the LabVIEW Front Panel according to their needs. When using the full power of all four Application Engines in Convey HC-1, users can feed up to 800 query sequence elements into the pipelines, and stream through a database at any length.
Fig 2. ConVI Pipeline Wrapper
With the following LabVIEW front panel, users are able to pick their preferred configuration for each AE, and load reference sequences and query sequences locally. With the ease of clicking the “GO” button, a set of commands will be sent for configuring the ConVI pipeline wrapper and locating datas. Also, a group of status LEDs are able to notify the users whether the configurations are acceptable.
Fig 3. LabVIEW Front Panel
As shown in Fig 4, using ConVI hardware accelerator would result in a significant improvement in the performance of computing sequence alignment with Smith Waterman algorithm. The tests were performed with 50 query sequences streaming through a database of size 1000. It only took ConVI about 2.1ms to execute the computation and 17.5ms to load data. However, it would take the LabVIEW software running on the host about 540ms to complete the whole process. The speedup could become even more considerable when the size of query sequence and the size of database are increased. The challenge of this hardware accelerator is to move the data quickly and to retain the computational accuracy.
Fig 4. Execution Time Comparison between Software and Hardware