Reconfigurable architecture structures for the BLAST DNA sequencing algorithm

Abstract

Computational Molecular Biology or Bioinformatics is an emerging area for Electronic and Computer Engineering. Bioinformatics research results are expected to have a great impact on Biology and on Medical research, leading to new medicines or treatments for several diseases. The Bioinformatics area consists of several algorithms and datasets, leading to computationally challenging problems. Datasets have exponentially grown in size over the last few years, and the trend continues. Thealgorithms have several variations, depending on the size and the nature of datasets. Several algorithms are usually combined to solve bioinformatics problems. The BLAST algorithm is considered to be the most widely used one in the Bioinformatics community, and is used in many Bioinformatics problems, e.g. to find similarity between fragments of genetic data (query) and an organism (database), even if there are mutations or data that are not properly decoded (non exact match algorithm). Reconfigurable logic has been used in numerous problems to accelerate theexecution time of many applications, FPGAs have been previously used to map exact matching algorithms or less sophisticated Βioinformatics algorithms vs. BLAST. This dissertation presents a system based on reconfigurable logic to implement the BLAST algorithm, regardless of data size or algorithm variation. The BLAST algorithm has been studied in depth and the corresponding architectures have been designed and evolved in four different generations. The architectures are original and unique in offering a completely general solution for all BLAST variations. All architectures have been thoroughly post place and route simulated and the results have been confirmed against results of the most broadly accepted version of software (the NCBI BLAST). In addition, a laboratory prototype system has been build on an off-theshelf platform and all major technical implementation problems have been solved, including I/O issues. The TUC BLAST system, which is presented in this work, is one to three orders of magnitude faster than a general purpose computer running the BLAST algorithm.