James W. Lindelien, Robert Farrington, Betty Tjandra
Time Logic, Inc., 11992 Challenger Ct., Moorpark, CA 93021; and 567 Knotty Pine Dr., Incline Village, NV 89451. Email to firstname.lastname@example.org
With government funding incentives to reduce the cost per sequenced base an order of magnitude by the year 2000, the informatics bottleneck must be addressed economically or further scale-up of massive sequencing projects will be significantly hindered. We have developed a transformable array accelerator based on Field-Programmable-Logic-Array (FPGA) technology for high-speed searches of massive nucleic and protein databases that is one to two orders of magnitude less expensive than present systems yet yields the world's fastest Smith-Waterman implementation. We hope to promote discovery by allowing more analysis per research dollar, by more biologists. The ability to retrieve search results in seconds permits a more creative "what-if" style of interactive database exploration, versus conventional but tedious "batch" style searches. System performance is scalable over 100x.
Multiple search processors are configured within an on-card FPGA array. Less computationally intensive algorithms run up to 10x faster than Smith-Waterman due to increased on-chip parallelism. Since the on-chip wiring of FPGAs can be set by software configuration h1 a fraction of a second, the array is readily transformed for a variety of search algorithms, or to first "pre-screen" large query sets with a higher speed (but less sensitive) algorithm to yield a higher daily throughput. The algorithms are:
|IUB/GCG-16 Symbol Set; ktup=1. Dual scoring: k-tuple length, and max. % matches in user set "bin" size of 16 to 512 bases/bin (powers of 2).||1.28 Billion nt-nt|
|Amino Acid-to-Amino Acid|
|Using 5 bit 32x32 programmable matrix; ktup=1. Dual scoring: k-tuple length, and max. % matches in user set "bin" size of 16 to 512 residues/bin (powers of 2).||320 Million aa-aa|
|Smith-Waterman||User Programmable similarity matrix; affine gap scoring to 16 bit resolution.||100 Million S-W matrix|
|Profile Search||User programmable similarity matrix; affine gap scoring to 16 bit resolution.||100 Million matrix |
|User programmable similarity matrix; and affine gap scoring. Searches 3 nt frames vs. aa target simultaneously with user set frame shift and gap penalties.||100 Million S-W matrix|
|User programmable similarity matrix; and affine gap scoring. Searches 3 nt frames vs. aa target simultaneously with user set frame shift and gap penalties.||100 Million matrix|
For high-volume sequencing projects, the multiple query, single target design accepts in bulk the query sets produced by automated sequencers. Simultaneous processing of many short queries creates a larger "effective query size." This decouples the computation rate of the FPGA array from the disk read bandwidth, permitting very high performance without a disk bottleneck, nor the usual requirement to RAM-cache the target database. Typical Pentium-based computers with low-cost disk systems (EIDE. SCSI-2) support Smith-Waterman searches on up to 15 accelerator cards per PC, at an aggregate rate of 1.5 billion SW cells/second. Such a PC is about 110% the speed of the MasPar MP-2 16384 processor supercomputer but costs only 4% as much, and requires no annual support contract. Still higher performance is achieved by TCP/IP (NFS) network clustering. We offer individual cards and development assistance to academic researchers having other applications for the technology.
This project was privately funded by Time Logic, Inc.
Return to Table of Contents