2007 · 13 citations · 18 references
EngineeringBioinformaticsComputer EngineeringField-programmable Gate ArraysReconfigurable ComputingSequence AnalysisFpga ArchitectureHardware AccelerationReconfigurable AcceleratorsReconfigurable System ArchitectureSequence AlignmentSequence Similarity SearchAlignment OptimizationBiological Sequence AlignmentReconfigurable Hardware ArchitectureSequence ComparisonSequence Similarity ScoringSimilarity Scoring FunctionsSmith - Waterman AlgorithmSmith-waterman Algorithm
DNA sequence alignment is a very important problem in bioinformatics. The algorithm proposed by Smith-Waterman (SW) is an exact method that obtains optimal local alignments in quadratic space and time. For long sequences, quadratic complexity makes the use of this algorithm impractical. In this scenario, the use of a reconfigurable architecture is a very attractive alternative. This article presents the design and evaluation of an FPGA-based architecture that obtains the similarity score between DNA sequences, as well as its coordinates. The results obtained in a Xilinx xc2vp70 FPGA prototype presented a speedup of 246.9 over the software solution to compare sequences of size 100 MBP and 100 BP, respectively. Different from others hardware solutions that just calculate alignment scores, our design was able to avoid architecture's bottlenecks and accelerate the most computer intensive part of a sequence alignment software algorithm.
18
Basic local alignment search tool
Stephen F. Altschul, Warren Gish, Webb Miller et al. · Journal of Molecular Biology · 1990 · 94.5K citations
Basic Local Alignment Search Tool
Stephen F. Altschul · Journal of Molecular Biology · 1990 · 13.9K citations