title: An optimized and low-cost FPGA-based DNA sequence alignment--a step towards personal genomics.
abstract: DNA sequence alignment is a cardinal process in computational biology but also is much expensive computationally when performing through traditional computational platforms like CPU. Of many off the shelf platforms explored for speeding up the computation process, FPGA stands as the best candidate due to its performance per dollar spent and performance per watt. These two advantages make FPGA as the most appropriate choice for realizing the aim of personal genomics. The previous implementation of DNA sequence alignment did not take into consideration the price of the device on which optimization was performed. This paper presents optimization over previous FPGA implementation that increases the overall speed-up achieved as well as the price incurred by the platform that was optimized. The optimizations are (1) The array of processing elements is made to run on change in input value and not on clock, so eliminating the need for tight clock synchronization, (2) the implementation is unrestrained by the size of the sequences to be aligned, (3) the waiting time required for the sequences to load to FPGA is reduced to the minimum possible and (4) an efficient method is devised to store the output matrix that make possible to save the diagonal elements to be used in next pass, in parallel with the computation of output matrix. Implemented on Spartan3 FPGA, this implementation achieved 20 times performance improvement in terms of CUPS over GPP implementation.
authors.forename: Hurmat Ali
authors.initials: HA
authors.lastname: Shah
authors.forename: Laiq
authors.initials: L
authors.lastname: Hasan
authors.forename: Nasir
authors.initials: N
authors.lastname: Ahmad
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000191:economics* / Q000379:methods*; D004247:DNA / Q000737:chemistry* / Q000378:metabolism; D023281:Genomics; D059014:High-Throughput Nucleotide Sequencing / Q000191:economics; D006801:Humans; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA
chemical_list: D004247:DNA