|
Title:
|
PARALELL COMPUTATION OF GENE SEQUENCE MATCHING |
|
Author(s):
|
G. Caffarena , S. Bojanic , J.a. López , C. Pedreira , O. Nieto-taladriz |
|
ISBN:
|
972-98947-3-6 |
|
Editors:
|
Nuno Guimarães and Pedro Isaías |
|
Year:
|
2004 |
|
Edition:
|
Single |
|
Keywords:
|
Bioinformatics, Smith-Waterman algorithm, gene matching, FPGA, parallel architectures, accelerator boards. |
|
Type:
|
Full Paper |
|
First Page:
|
1018 |
|
Last Page:
|
1025 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
One of the main challenges in bioinformatics nowadays is to create a framework to compare efficiently new DNA sequence information to large existing sequence and structure databases. Optimal methods, such as the Smith-Waterman algorithm, provide more sensitive results than heuristic algorithms such as the Dot matrix plot, FASTA and BLAST, with the drawback of increased computational complexity. FPGA implementations of Smith-Waterman exploit the intrinsic parallelism of the algorithm and achieve reductions in computation time of several orders of magnitude. In this paper we propose an implementation of the Smith-Waterman algorithm based on a linear systolic array that doubles the speed of current approaches with a minimum increase of area. The design was performed taking into account the bus I/O bottleneck (i.e. PCI), so the processing speed improvement is still available even when the systolic array is connected to a bus. The implementation results on Xilinx Virtex and Virtex2 FPGA families are also presented. |
|
|
|
|
|
|
