Reconfigurable architecture structures for the BLAST DNA sequencing algorithm

Reconfigurable architecture structures for the BLAST DNA sequencing algorithm

Sotiriades, Euripides

Σωτηριάδης, Ευριπίδης

PhD Thesis

2011

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.

Φυσικές Επιστήμες ➨ Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική

Επιστήμες Μηχανικού και Τεχνολογία ➨ Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ

Nucleotide sequence

Field programmable gate arrays (FPGA)

Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ

Electrical Engineering, Electronic Engineering, Information Engineering

Data processing

Computer and Information Sciences

Φυσικές Επιστήμες

Επιστήμες Μηχανικού και Τεχνολογία

Engineering and Technology

Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική

Natural Sciences

Molecular biology

Bioinformatics

Αγγλική γλώσσα

Πολυτεχνείο Κρήτης

Technical University of Crete (TUC)

Πολυτεχνείο Κρήτης. Σχολή Ηλεκτρονικών Μηχανικών και Μηχανικών Υπολογιστών

Εθνικό Κέντρο Τεκμηρίωσης και Ηλεκτρονικού Περιεχομένου (ΕΚΤ)

Εθνικό Αρχείο Διδακτορικών Διατριβών

Συλλογή ΕΑΔΔ