An implementation of the basic local alignment search tool (Blast) for nucleotides. The goal of this project is to implement the BLASTn algorithm in C++ and interop with an FPGA implementation of the Smith-Waterman algorithm to greatly accelerate the word extension stage of BLASTn.
The BLASTn algorithm performs operations on DNA sequences in several steps, which together make up the parts of the algorithm. The process in which BLASTn operates is shown in Fig. 1.
Fig. 1. The BLASTn process
Electrical and Computer Engineering Senior Project at California State Polytechnic University, Pomona
- Alden Param
- Alex Chan
- Hmayak Apetyan
- Jacob London
- Simon Tutak
- Sivaramakrishnan Prabakar
- Mohamed El-Hadedy: Assistant Professor, Electrical and Computer Engineering department, College of Engineering, California State Polytechnic University, Pomona.
- Mostafa M. Hashim Ellabaan: Senior Researcher, Novo Nordisk Foundation Center for Biosustainability, Technical University of Denmark.
Collaborators:
1. Wen-Mei Hwu: Director of Center for Cognitive Computing Systems Research and Walter J. Sanders III-AMD Endowed Chair Professor in Elecrical and Computer Engineering at UIUC
2. Jinjun Xiong: Director of Center for Cognitive Computing Systems Research and Adjunct Research Professor at UIUC
# HTTPS
$ git clone https://github.com/Reconfigurable-Computing-CalPoly-Pomona/Reconfigurable-BLAST-N.git --recurse-submodules
# SSH
$ git clone git@github.com:Reconfigurable-Computing-CalPoly-Pomona/Reconfigurable-BLAST-N.git --recurse-submodules
For the Docker container, run docker build -t blastn . to create the environment with all necessary dependencies. BLASTn will be placed under /root. For building the C++ system, see the C++ README.
| Implementation | Dependency |
|---|---|
| GNU C++ | C++17, g++7.4+, GNU Make 4.2.1+ |
| Visual C++ | Visual Studio Suite 2019 |
| Python | Python 3.6+, pip3, numpy, tqdm |
| Vivado | Vivado 2019.1 |
Future work would entail implementing the entire BLASTn algorithm on the FPGA. Although the majority of performance gain can be accomplished by hardware accelerating the Smith-Waterman portion of the algorithm, there is value in having the entire algorithm running end to end on the board. The bottleneck in the process is the transmission rate of data between the computer and the FPGA, something that could be solved in two different ways. The first is to have the entire algorithm run on the FPGA. The second would be to use a faster communication method, such as PCIE. Additionally, there is still some benchmarking that could be done to show the true speed of our implementation. More runtimes could be tested by testing our algorithm on multiple FPGAs, and even creating arrays of FPGAs to try to see how fast our version of BLASTn could run. Another improvement to this project could be on the implementation of the Smith-Waterman algorithm itself. During our hardware implementation of the Smith-Waterman, we came up with a few different promising ideas that could result in a speed-up. Unfortunately, we had to abandon these ideas in the interest of time and choose our stable, but slower, implementation of Smith-Waterman (that was successfully implemented on the FPGA). Additionally, during our implementation of the Smith Waterman Algorithm in VHDL, we were unable to properly simulate propagation delay. Unfortunately, the digital logic does not capture the delays that would occur in our real-world implementation. This could be addressed by an FPGA implementation that accounts for analog properties such as propagation delay between gates. As a result, our simulation displays an immediate reaction and does not properly illustrate the implementation we developed.