Method and apparatus for performing similarity searching on a data stream with respect to a query string

• US 7,917,299 B2
• Filed: 02/22/2006
• Issued: 03/29/2011
• Est. Priority Date: 03/03/2005
• Status: Active Grant

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Chamberlain, Roger Dean, Gyang, Kwame, Buhler, Jeremy Daniel, Jacob, Arpith Chacko, Krishnamurthy, Praveen, Lancaster, Joseph Marion, Franklin, Mark Allen
• Primary Examiner(s): Zeman; Mary K
• Application Number:
  US11/359,285
• Publication Number:
  US 20070067108A1
• Time in Patent Office: 1,861 Days
• Field of Search: None
• US Class Current: 702/19
• 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

An apparatus and method for performing similarity searching on a data stream with respect to a query string are disclosed, where the data stream comprises a plurality of data substrings, and where the query string comprises a plurality of query substrings. A programmable logic device is used to filter the data stream to find a plurality of possible matches between the data substrings and a plurality of the query substrings, wherein the data substrings and the query substrings comprise a plurality of characters. From these possible matches, a determination can be made as to a similarity between the query string and at least a portion of the data stream.

Claims

1. A method for performing similarity searching on a data stream with respect to a query string, the data stream comprising a plurality of data substrings, the query string comprising a plurality of query substrings, the method comprising:

filtering the data stream using a programmable logic device configured to find a plurality of possible matches between the data substrings and a plurality of the query substrings,

wherein the data substrings and the query substrings comprise a plurality of characters;

for each data substring that was found to be a possible match as a result of the filtering step, identifying at least one corresponding query substring for which that data substring is a possible match; and

determining a similarity between the query string and at least a portion of the data stream based on the possible matches found by the filtering step, wherein the determining step comprises (1) comparing the characters of a window of the data stream that encompasses the data substring found to be a possible match with the characters of a window of the query string that encompasses the identified query substring corresponding to the data substring that was found to be a possible match, and (2) assessing whether the data stream portion and the query string qualify as being similar to each other based on the comparing step such that a controlled number of mismatches are permitted between the characters of the data stream window and the characters the query string window.

2. The method of claim 1 wherein the filtering step comprises filtering the data stream with a Bloom filter.

3. The method of claim 2 wherein the Bloom filter comprises an array of Bloom filters, the Bloom filters being programmed with the query substrings.

4. The method of claim 3 wherein the array comprises a plurality of parallel Bloom filters, each of the parallel Bloom filters being programmed with the same query substrings.

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

6. The method of claim 1 further comprising performing the identifying and the determining steps with the programmable logic device.

7. The method of claim 1 wherein the data stream comprises biosequence data.

8. The method of claim 1 wherein the data substrings comprise overlapping data substrings.

9. The method of claim 8 further comprising:

generating the overlapping data substrings from the data stream.

10. The method of claim 1 wherein the query substrings comprise overlapping query substrings.

11. The method of claim 1 wherein the identifying step comprises performing the identifying step with hashing logic.

12. The method of claim 1 wherein the identifying step comprises performing the identifying step with the programmable logic device.

13. The method of claim 1 wherein the identifying step comprises:

identifying a pointer to a position in the data stream for the data substring that was found to be a possible match; and

identifying a pointer to a position in the query string for the query substring corresponding to the data substring that was found to be a possible match.

14. The method of claim 1 wherein the assessing step comprises controlling the controlled number of mismatches via a scoring mechanism that rewards character matches and penalizes character mismatches.

15. An apparatus for performing similarity searching on a data stream with respect to a query string, the data stream comprising a plurality of data substrings, the query string comprising a plurality of query substrings, the apparatus comprising:

a programmable logic device configured to;

(1) filter the data stream to find a plurality of possible matches between the data substrings and a plurality of the query substrings, wherein the data substrings and the query substrings comprise a plurality of characters, (2) for each data substring that was found to be a possible match as a result of the filtering operation, identify at least one corresponding query substring for which that data substring is a possible match, and (3) determine a similarity between the query string and at least a portion of the data stream based on the filtered possible matches by (i) comparing the characters of a window of the data stream that encompasses the data substring found to be a possible match with the characters of a window of the query string that encompasses the identified query substring corresponding to the data substring that was found to be a possible match, and (ii) assessing whether the data stream portion and the query string qualify as being similar to each other based on the comparison such that a controlled number of mismatches are permitted between the characters of the data stream window and the characters the query string window.

16. The apparatus of claim 15 wherein the programmable logic device is further configured to filter the data stream with a Bloom filter.

17. The apparatus of claim 16 wherein the Bloom filter comprises an array of Bloom filters, the Bloom filters being programmed with the query substrings.

18. The apparatus of claim 17 wherein the array comprises a plurality of parallel Bloom filters, each of the parallel Bloom filters being programmed with the same query substrings.

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

20. The apparatus of claim 15 wherein the data stream comprises biosequence data.

21. The apparatus of claim 15 wherein the data substrings comprise overlapping data substrings.

22. The apparatus of claim 21 wherein the programmable logic device is further configured to generate the overlapping data substrings from the data stream.

23. The apparatus of claim 15 wherein the query substrings comprise overlapping query substrings.

24. The apparatus of claim 15 wherein the programmable logic device is further configured to perform the identification operation with hashing logic.

25. The apparatus of claim 15 wherein the programmable logic device is further configured to perform the identification operation by:

identifying a pointer to a position in the data stream for the possibly matching data substring that was found to be a possible match; and

identifying a pointer to a position in the query string for the query substring corresponding to the data substring that was found to be a possible match.

26. The apparatus of claim 15 wherein the programmable logic device is further configured to control the controlled number of mismatches via a scoring mechanism that rewards character matches and penalizes character mismatches.