Digital logic implementation of DNA comparison algorithm: A hardware implementation of smith - waterman algorithm

Abstract

DNA is the main target of bioinformatics since it stores the genetic information that influences the most important characteristics of an organism. Dealing with DNA is not a simple issue. The main problem is that DNA is a huge data-structure. Traditionally, only supercomputers could deal with it. However, recent research has proposed to develop hardware implementations of the available comparison algorithms using programmable hardware devices, such as FPGAs. Continuing to my senior project with the demand of a high – speed DNA sequence comparisons, frequently comparing a given DNA sequence with the sequences stored in large scientific databases, the purpose of this project is implementation the digital logic to perform a DNA comparison based on the commonly used Smith-Waterman algorithm. I will build the digital logic from a basic logic cell which i have done from my senior project which can compares a pair of nucleobases and calculates the mutation-distance between them. Base on the hierarchical design i will reuse the basic cell from the senior project to design a 2x2 matrix that compares two small sequences of two nucleobases each. Analysis of 2x2 will be used to identify what must be changed to reuse the same approach for lager systems. Using the data obtained after implementing the basic cell, i will build a theoretical model to evaluate the efficiency of my design for lager matrices. After designing the system i will simulate the design using both Functional simulation and Post-Place & Route simulation using the same test bench for both simulations. I will simulate the design , implement it, and test it in an FPGA. The results of this project is measurement the performance, the speed of the FPGA implementation compared with a software implementation of the Smith-Waterman algorithm.