Method and apparatus for performing similarity searching

• US 9,547,680 B2
• Filed: 08/19/2013
• Issued: 01/17/2017
• Est. Priority Date: 03/03/2005
• Status: Expired due to Fees

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Buhler, Jeremy Daniel, Chamberlain, Roger Dean, Franklin, Mark Allen, Gyang, Kwame, Jacob, Arpith Chacko, Krishnamurthy, Praveen, Lancaster, Joseph Marion
• Primary Examiner(s): ZEMAN, MARY K
• Application Number:
  US13/969,935
• Publication Number:
  US 20140067830A1
• Time in Patent Office: 1,247 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G16B 30/00 ICT specially adapted for sequence analysis involving nucleotides or amino acids
• CPC Class Codes: G16B 30/10 Sequence alignment; Homology search
• CPC Class Codes: G16B 50/00 ICT programming tools or database systems specially adapted for bioinformatics
• CPC Class Codes: G16B 50/30 Data warehousing; Computing architectures

Abstract

A system and method for performing similarity searching is disclosed wherein programmable logic devices such as field programmable gate arrays (FPGAs) can be used to implement Bloom filters for identifying possible matches between a query and data. The Bloom filters can be implemented in a parallel architecture where the different parallel Bloom filters share access to the same memory units.

Claims

1. A system comprising:

a programmable logic device configured to perform similarity searching between a first data string and a second data string, the first data string comprising a plurality of first data substrings, the second data string comprising a plurality of second data substrings, the programmable logic device comprising a plurality of parallel Bloom filters;

wherein the Bloom filters are programmed with the second data substrings and are configured to process the first data substrings to determine whether any possible matches exist between the first data substrings and the second data substrings;

wherein each Bloom filter comprises a hash component, a plurality of dual port memory units downstream from the hash component, and a logic component downstream from the dual port memory units; and

wherein a plurality of the Bloom filters share access to a plurality of the same dual port memory units.

2. The system of claim 1 wherein the dual port memory units are clocked to replicate a number of ports for the dual port memory units greater than two.

3. The system of claim 2 wherein each hash component comprises a plurality of hash functions, each hash function corresponding to a dual port memory unit such that each dual port memory unit corresponds to a plurality of hash functions of different hash components;

wherein each dual port memory unit is configured to store a bit vector;

wherein the Bloom filters are configured to be programmed by (1) applying the second data substrings to the hash functions to map the second data substrings to a plurality of bit locations in the bit vectors of the corresponding dual port memory units, and (2) setting the bits at the mapped bit locations; and

wherein the Bloom filters are configured to determine whether any possible matches exist between the first data substrings and the second data substrings by (1) applying the first data substrings to the hash functions to map the first data substrings to a plurality of bit locations in the bit vectors of the corresponding dual port memory units, (2) applying a plurality of bit values from the mapped bit locations to the logic component to determine whether all of the bit values are set.

4. The system of claim 3, wherein each of the plurality of parallel Bloom filters are programmed with the same second data substrings.

5. The system of claim 3 wherein the logic component for each Bloom filter comprises an AND gate.

6. The system of claim 1 wherein the dual port memory units are double clocked to replicate a plurality of four port memory units, each double clocked dual port memory unit being shared by four of the Bloom filters.

7. The system of claim 1 wherein the dual port memory units are triple clocked to replicate a six port memory unit, each triple clocked dual port memory unit being shared by six of the Bloom filters.

8. The system of claim 1 wherein the first data string and the second data string comprise biosequence data strings.

9. The system of claim 1 wherein the programmable logic device comprises a field programmable gate array (FPGA).

10. The system of claim 2 wherein the first data string and the second data string comprise biosequence data strings.

11. The system of claim 2 wherein the programmable logic device comprises a field programmable gate array (FPGA).

12. The system of claim 3 wherein the first data string and the second data string comprise biosequence data strings.

13. The system of claim 3 wherein the programmable logic device comprises a field programmable gate array (FPGA).

14. The system of claim 4 wherein the first data string and the second data string comprise biosequence data strings.

15. The system of claim 4 wherein the programmable logic device comprises a field programmable gate array (FPGA).

16. The system of claim 5 wherein the first data string and the second data string comprise biosequence data strings.

17. The system of claim 5 wherein the programmable logic device comprises a field programmable gate array (FPGA).

18. The system of claim 6 wherein the first data string and the second data string comprise biosequence data strings.

19. The system of claim 6 wherein the programmable logic device comprises a field programmable gate array (FPGA).

20. The system of claim 7 wherein the first data string and the second data string comprise biosequence data strings.

21. The system of claim 7 wherein the programmable logic device comprises a field programmable gate array (FPGA).

22. The system of claim 8 wherein the programmable logic device comprises a field programmable gate array (FPGA).

23. The system of claim 1, wherein each of the plurality of parallel Bloom filters are programmed with the same second data substrings.

24. The system of claim 23 wherein the first data string and the second data string comprise biosequence data strings.

25. The system of claim 23 wherein the programmable logic device comprises a field programmable gate array (FPGA).

26. The system of claim 1 wherein the logic component for each Bloom filter comprises an AND gate.

27. The system of claim 26 wherein the first data string and the second data string comprise biosequence data strings.

28. The system of claim 26 wherein the programmable logic device comprises a field programmable gate array (FPGA).