Method and Apparatus for Performing Similarity Searching

Abstract

Apparatuses and methods are disclosed for comparing a first biosequence string with a second biosequence string to assess similarity between those biosequence strings. For example, a field programmable gate array (FPGA) can be used to (1) detect substrings of the second biosequence string that are matches to substrings of the first biosequence string, and (2) map the detected substrings of the second biosequence string to corresponding positions in the first biosequence string where the detected substrings are located based on a data structure that links substrings of the first biosequence string to positions in the first biosequence string where the substrings of the first biosequence string are located. These operations can be used to seed an alignment between the first and second biosequence strings that permits comparisons to be performed over longer substrings of the first and second biosequence strings so that similarities between those longer substrings can be quantified.

What is claimed is: 
     
         1 . A method for comparing a first biosequence string with a second biosequence string to assess similarity between the first and second biosequence strings, the method comprising:
 a field programmable gate array (FPGA) detecting substrings of the second biosequence string that are matches to substrings of the first biosequence string; and   the FPGA mapping the detected substrings of the second biosequence string to corresponding positions in the first biosequence string where the detected substrings are located based on a data structure that links substrings of the first biosequence string to positions in the first biosequence string where the substrings of the first biosequence string are located.   
     
     
         2 . The method of  claim 1  further comprising accessing the data structure in a memory to support the mapping. 
     
     
         3 . The method of  claim 2  wherein the memory is resident on the FPGA. 
     
     
         4 . The method of  claim 2  wherein the memory is off-chip from the FPGA. 
     
     
         5 . The method of  claim 1  wherein the data structure comprises a hash table. 
     
     
         6 . The method of  claim 1  wherein the matches include false positive matches with respect to the first biosequence string. 
     
     
         7 . The method of  claim 6  wherein the FPGA comprises a Bloom filter, and wherein the detecting step comprises the Bloom filter detecting substrings of the second biosequence string that are possible matches to substrings of the first biosequence string. 
     
     
         8 . The method of  claim 6  wherein the mapping step eliminates a plurality of false positives from the detected substrings, and wherein the eliminated false positives correspond to detected substrings that are not linked by the data structure to positions in the first biosequence string. 
     
     
         9 . The method of  claim 8  wherein the data structure comprises a hash table, and wherein the eliminated false positives are detected substrings of the second biosequence string that are linked to empty entries in the hash table. 
     
     
         10 . The method of  claim 1  wherein the FPGA is configured as a multistage pipeline that includes pipeline stages for performing the detecting and mapping steps on a stream of the second biosequence string. 
     
     
         11 . The method of  claim 10  wherein the multistage pipeline provides BLAST Stage 1 operations. 
     
     
         12 . The method of  claim 1  wherein the first biosequence string is a query sequence of DNA bases, and wherein the second biosequence string is a database sequence of DNA bases. 
     
     
         13 . The method of  claim 1  wherein the FPGA further comprises an ungapped extension filter, the method further comprising:
 the FPGA applying the detected and mapped substrings to the ungapped extension filter. 
 
     
     
         14 . The method of  claim 13  further comprising:
 the FPGA identifying (1) windows of the second biosequence string around the detected and mapped sub strings and (2) corresponding windows of the first biosequence string around the mapped positions for the detected and mapped substrings. 
 
     
     
         15 . The method of  claim 14  further comprising:
 the ungapped extension filter quantifying a similarity between pairs of longer substrings of the first and second biosequence strings within the identified corresponding windows; and 
 the ungapped extension filter identifying the pairs for which the quantified similarity is above a threshold. 
 
     
     
         16 . The method of  claim 1  further comprising:
 the FPGA generating a plurality of partially overlapping substrings of the second biosequence string; and 
 the FPGA performing the detecting step on the partially overlapping substrings to detect the matches to substrings of the first biosequence string. 
 
     
     
         17 . A method for comparing a first biosequence string with a second biosequence string to assess similarity between the first and second biosequence strings, the method comprising:
 a field programmable gate array (FPGA) processing a stream of the second biosequence string through a pipeline resident on the FPGA;   wherein the processing step comprises:
 the pipeline mapping positions within the first and second biosequence strings to each other based where matches exist within the first and second biosequence strings between substrings of the first and second biosequence strings; and 
 based on the mapped positions of the first and second biosequence strings, the pipeline finding an alignment between longer substrings of the first and second biosequence substrings for which a similarity between the aligned longer substrings is above a threshold. 
   
     
     
         18 . The method of  claim 17  wherein the first biosequence string is a query sequence of DNA bases, and wherein the second biosequence string is a database sequence of DNA bases. 
     
     
         19 . An apparatus for comparing a first biosequence string with a second biosequence string to assess similarity between the first and second biosequence strings, the apparatus comprising:
 a field programmable gate array (FPGA), wherein the FPGA is configured to (1) compare a first substring of the first biosequence string with a first substring of the second biosequence string to quantify a similarity between the first substring of the first biosequence string and the first substring of the second biosequence string, (2) seed the comparison operation by detecting a position within the first biosequence substring and a position within the second biosequence substring which correspond to second substrings of the first and second biosequence strings respectively that match each other, wherein the first substrings are longer than the second substrings, and (3) perform the seeding and comparison operations with respect to a plurality of different substrings of the first and second biosequence strings.   
     
     
         20 . The apparatus of  claim 19  wherein the first biosequence string is a query sequence of DNA bases, and wherein the second biosequence string is a database sequence of DNA bases.