|
Title:
|
A SYSTOLIC ARRAY ARCHITECTURE FOR THE SMITH-WATERMAN ALGORITHM WITH HIGH PERFORMANCE CELL DESIGN |
|
Author(s):
|
Laiq Hasan , Yahya M. Khawaja , Abdul Bais |
|
ISBN:
|
978-972-8924-63-8 |
|
Editors:
|
Hans Weghorn and Ajith P. Abraham |
|
Year:
|
2008 |
|
Edition:
|
Single |
|
Keywords:
|
Bioinformatics, Sequence Alignment, Dynamic Programming, Smith-Waterman Algorithm, FPGAs, Systolic Arrays |
|
Type:
|
Full Paper |
|
First Page:
|
35 |
|
Last Page:
|
42 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
To infer homology and subsequently gene function, the Smith-Waterman (S-W) algorithm is used to find the optimal local
alignment between two sequences. When searching sequence databases that may contain hundreds of millions of
sequences, this algorithm becomes computationally expensive. In this paper, we present a systolic array architecture for
the S-W algorithm with a new high performance cell design. The results demonstrate that the implementation of this
architecture achieves a speedup of up to 652x, as compared to a software-only implementation, which is almost double
the best case reported in the literature. The results also demonstrate that when mapped on the same FPGA platform, our
design performs 1.47 to 5.75 times faster in terms of Cell Updates Per Second (CUPS), in comparison with other
published systolic array designs, while utilizing 3.69 to 6.36 times less resources. |
|
|
|
|
|
|
