Method and apparatus for performing biosequence similarity searching

• US 20070067108A1
• Filed: 02/22/2006
• Published: 03/22/2007
• Est. Priority Date: 03/03/2005
• Status: Active Grant

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Gyang, Kwame, Krishnamurthy, Praveen, Buhler, Jeremy, Lancaster, Joseph, Jacob, Arpith, Chamberlain, Roger, Franklin, Mark
• Granted Patent: US 7,917,299 B2
• Time in Patent Office: Days
• 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

A system and method for performing biological sequence similarity searching is disclosed. This includes a programmable logic device configured to include a pipeline that comprises a matching stage, the matching stage being configured to receive a data stream comprising a plurality of possible matches between a plurality of biological sequence data strings and a plurality of substrings of a query string. The pipeline may further include a ungapped extension prefilter stage located downstream from the matching stage, the prefilter stage being configured to shift through pattern matches between the biological sequence data strings and the plurality of substrings of a query string and provide a score so that only pattern matches that exceed a user defined score will pass downstream from the prefilter stage. The matching stage may include at least one Bloom filter.

Claims

1. A digital logic circuit for performing biological sequence similarity searching, the circuit comprising:

a programmable logic device configured to include a pipeline comprising a Bloom filter stage, the Bloom filter stage being configured to receive a data stream comprising a plurality of biological sequence data strings and filter the biological sequence data stream to identify a plurality of possible matches between the sequence data strings and a plurality of substrings of a query string.

2. The circuit of claim 1, wherein the programmable logic device comprises a FPGA.

3. The circuit of claim 2, wherein the biological sequence similarity searching pipeline comprises a first stage for BLAST.

4. The circuit of claim 3, wherein the BLAST first stage comprises a first stage for BLASTN.

5. The circuit of claim 3, wherein the BLAST first stage comprises a first stage for one selected from the group consisting of BLASTP, BLASTX, TBLASTN, and TBLASTX.

6. The circuit of claim 3, wherein the Bloom filter stage comprises a plurality of parallel Bloom filters.

7. The circuit of claim 6, wherein the plurality of parallel Bloom filters are programmed with a plurality of query substrings prior to processing the biological sequence data stream through the pipeline.

8. The circuit of claim 7, wherein each of the plurality of parallel Bloom filters are programmed with the same query substrings.

9. The circuit of claim 8, wherein each Bloom filter is configured to access a dual port BRAM on the FPGA, wherein the dual port BRAM is double clocked to replicate a four port BRAM.

10. The circuit of claim 9, wherein access to each dual port BRAM is shared by four parallel Bloom filters.

11. The circuit of claim 8, wherein each Bloom filter is configured to access a dual port BRAM on the FPGA, wherein the dual port BRAM is triple clocked to replicate a six port BRAM.

12. The circuit of claim 11, wherein access to each dual port BRAM is shared by at least six parallel Bloom filters.

13. The circuit of claim 8, wherein each Bloom filter is configured to utilize k hash functions and k (1×

m) bit memory units, each memory unit corresponding to one of that Bloom filter'"'"'s hash functions, each hash function being configured to map received sequence strings to bits in its corresponding memory unit to determine if a possible match exists.

14. The circuit of claim 13, wherein each memory unit comprises a dual port BRAM unit.

15. The circuit of claim 13, wherein access to each dual port BRAM unit is shared by a plurality of the Bloom filters.

16. The circuit of claim 15, wherein each dual port BRAM unit is double clocked such that it is shared by at least four of the Bloom filters.

17. The circuit of claim 7, wherein the pipeline further comprises a hashing stage downstream from the Bloom filter stage, the hashing stage being configured to map the possible matches to at least one position within the query string.

18. The circuit of claim 17, further comprising a memory in communication with the hashing stage, the memory being configured to store a hash table, the hash table storing at least one pointer to a position in the query string for a possible match.

19. The circuit of claim 17, wherein the hashing stage comprises a perfect hashing stage.

20. The circuit of claim 17, wherein the hashing stage comprises a near perfect hashing stage.

21. The circuit of claim 20, wherein the near perfect hashing stage is configured with functions A and B selected from the H3 family of hash functions, wherein A and B are guaranteed to be of full rank.

22. The circuit of claim 17, further comprising a redundancy filter downstream from the hashing stage, the redundancy filter being configured to receive data representative of possible matches from the hashing stage and remove possible matches that are redundant with previous possible matches within a selectable degree of redundancy.

23. The circuit of claim 22, wherein the redundancy filter is implemented on the FPGA.

24. The circuit of claim 3, further comprising a database in communication with the FPGA, the database being configured to store a biological sequence that is to be streamed through the FPGA.

25. A system for performing seeded alignment searching, the system comprising:

a programmable logic device configured to implement a seeded alignment searching pipeline, the pipeline comprising a Bloom filter stage, the Bloom filter stage being configured to receive a data stream, the data stream comprising a plurality of data strings and filter the data stream to identify a plurality of possible matches between the stream data strings and a plurality of substrings of a query string.

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

27. A method for performing biological sequence similarity searching, the method comprising:

processing a biological sequence data stream through a Bloom filter stage implemented on a programmable logic device, the biological sequence data stream comprising a plurality of biological sequence data strings, the Bloom filter stage comprising a Bloom filter that is programmed with a plurality of substrings of a query string and configured to identify a plurality of possible matches between the biological sequence data strings and the query substrings.

28. The method of claim 27, wherein the Bloom filter is further configured to identify a position of each possible match within the biological sequence data stream.

29. The method of claim 28, wherein the programmable logic device comprises a FPGA.

30. The method of claim 29, further comprising performing the processing step as a portion of a first stage for BLAST.

31. The method of claim 30, wherein the BLAST first stage comprises a first stage for BLASTN.

32. The method of claim 30, wherein the BLAST first stage comprises a first stage for one selected from the group consisting of BLASTP, BLASTX, TBLASTN, and TBLASTX.

33. The method of claim 30, wherein the Bloom filter stage comprises a plurality of parallel Bloom filters.

34. The method of claim 33, further comprising:

programming the parallel Bloom filters with a plurality of query substrings prior to processing the biological sequence data stream through the Bloom filter stage.

35. The method of claim 33, wherein the programming step comprises programming each of the parallel Bloom filters with the same query substrings.

36. The method of claim 35, wherein the Bloom filter stage comprises a plurality of dual port BRAM units, the method further comprising double clocking the BRAM units to replicate a four port BRAM units.

37. The method of claim 36, wherein each dual port BRAM unit is accessed by four parallel Bloom filters.

38. The method of claim 35, wherein the Bloom filter stage comprises a plurality of dual port BRAM units, the method further comprising triple clocking the BRAM units to replicate a six port BRAM units.

39. The method of claim 38, wherein each dual port BRAM unit is accessed by six parallel Bloom filters.

40. The method of claim 34, further comprising mapping, via a hashing stage, each possible match from the Bloom filter stage to a position in the query string corresponding to the query substring that caused the possible match.

41. The method of claim 40, wherein the mapping step is performed at least partially by the FPGA.

42. The method of claim 41, wherein the mapping step comprises performing the mapping via a perfect hashing stage.

43. The method of claim 41, wherein the mapping step comprises performing the mapping via a near perfect hashing stage.

44. The method of claim 43, wherein the near perfect hashing stage is configured with functions A and B selected from the H3 family of hash functions, wherein A and B are guaranteed to be of full rank.

45. The method of claim 40, further comprising removing possible matches that are redundant with other possible matches within a selectable degree of redundancy.

46. The method of claim 45, wherein the removing step is performed at least partially by the FPGA.

47. A system for generating a hash table for use in mapping a set of strings to keys, the system comprising:

a processor configured to provide near perfect hashing on the set of strings to identify a location in a hash table, utilizing an H3 family of hash functions, corresponding to each string and to generate the hash table, the hash table being configured to store, at each identified location therein is a key; and

a memory in communication with the processor for storing the hash table, wherein the processor is configured to provide near perfect hashing via hash functions, utilizing the H3 family of hash functions, that are guaranteed to be of full rank.

48. A system for generating a hash table for use in mapping a set of substrings to a position in a larger string, the system comprising:

a processor configured to provide near perfect hashing on the set of substrings to identify a position in a hash table, corresponding to each substring and to generate the hash table, the hash table being configured to store, at each identified location therein, a pointer to a position of each substring in the larger string; and

a memory in communication with the processor for storing the hash table.

49. A digital logic circuit for performing biological sequence similarity searching, the circuit comprising:

a programmable logic device configured to include a pipeline that comprises a matching stage, the matching stage being configured to receive a data stream comprising a plurality of possible matches between a plurality of biological sequence data strings and a plurality of substrings of a query string and the pipeline further comprises a prefilter stage located downstream from the matching stage, the ungapped extension prefilter stage being configured to shift through pattern matches between the biological sequence data strings and the plurality of substrings of a query string and provide a score so that only pattern matches that exceed a user defined score will pass downstream from the ungapped extension prefilter stage.

50. The circuit of claim 49, wherein the programmable logic device comprises an FPGA.

51. The circuit of claim 49, wherein the matching stage comprises at least a portion of first stage for BLAST and the ungapped extension prefilter stage comprises at least a portion of a second stage for BLAST.

52. The circuit of claim 51, wherein the BLAST first stage is selected from the group consisting of a first stage for BLASTN, BLASTP, BLASTX, TBLASTN, and TBLASTX and the BLAST second stage is selected from the group consisting of a second stage for BLASTN, BLASTP, BLASTX, TBLASTN, and TBLASTX.

53. The circuit of claim 49, wherein the word matching stage further comprises a Bloom filter stage.

54. The circuit of claim 53, wherein the Bloom filter stage includes a plurality of Bloom filters.

55. The circuit of claim 53, wherein the word matching stage further comprises a hashing stage downstream from the Bloom filter stage, the hashing stage being configured to map the possible matches to at least one position within the query string.

56. The circuit of claim 55, further comprising a redundancy filter downstream from the hashing stage, the redundancy filter being configured to receive data representative of possible matches from the hashing stage and remove possible matches that are redundant with previous possible matches within a selectable degree of redundancy.

57. The circuit of claim 49, wherein the ungapped extension prefilter stage comprises an extension controller, a window lookup module and a scoring module.

58. The circuit of claim 49, wherein the ungapped extension prefilter stage utilizes parameters selected from the group consisting of a matching score, a mismatching score and a cutoff threshold.

59. The circuit of claim 49, wherein the ungapped extension prefilter stage comprises an extension controller.

60. The circuit of claim 59, wherein the extension controller comprises at least one of hardware, firmware and software.

61. The circuit of claim 59, wherein the extension controller comprises a plurality of data inputs including at least one first input for plurality of possible pattern matches of a predetermined length between a plurality of biological sequence data strings and a plurality of substrings of a query string and at least one second input for biological sequence data.

62. The circuit of claim 61, wherein at least one second input can receive commands for controlling parameters selected from the group consisting of a match score, a mismatch score or a cutoff threshold.

63. The circuit of claim 57, wherein the extension controller parses the biological data received by the at least one second input to demultiplex a shared command and the pattern matches of a predetermined length prior to submission into the window lookup module.

64. The circuit of claim 49, wherein the ungapped extension prefilter stage comprises a window lookup module.

65. The circuit of claim 64, wherein the window lookup module can fetch at least one substring of the biological sequence data and at least one substring of a query string to form a predefined window of biological data that can be utilized for analysis.

66. The circuit of claim 64, wherein the window lookup module receives at least one substring of the biological sequence data in a database buffer, at least one substring of a query string in a query buffer, an offset for at least one substring of the biological sequence data and an offset for at least one substring of a query string, wherein the window lookup module calculates a beginning of a window that is passed to a plurality of buffer modules, wherein the plurality of buffer modules move the at least one substring of a query string and the at least one substring of the biological sequence data to an output stage to create at least one predefined window of biological data that can be utilized for analysis.

67. The circuit of claim 65, wherein the at least one substring of the biological sequence data and at least one substring of a query string are buffered on a plurality of BRAMS.

68. The circuit of claim 49, wherein the ungapped extension prefilter stage comprises a scoring module.

69. The circuit of claim 68, wherein the scoring module is capable of fetching biological data within a predefined window.

70. The circuit of claim 69, wherein the scoring module utilizes at least one iteration of algorithm instructions.

71. The circuit of claim 68, wherein the scoring module further comprises a base comparator, a plurality of scoring stages and a threshold comparator.

72. The circuit of claim 68, wherein the scoring module further comprises a base comparator.

73. The circuit of claim 72, wherein the base comparator receives at least one pair of a substring of the biological sequence data and a substring of a query string and compares these values and obtains at least one comparison score.

74. The circuit of claim 73, wherein the at least one comparison score includes a positive value for each matching pair and a negative score for each mismatching pair.

75. The circuit of claim 73, wherein the at least one comparison score is substituted from values located on a lookup table.

76. The circuit of claim 68, wherein the scoring module further comprises a plurality of scoring stages.

77. The circuit of claim 76, further comprising discarding at least one comparison score from each subsequent downstream scoring stage of the plurality of scoring stages.

78. The circuit of claim 76, wherein at least one scoring stage of the plurality of scoring stages receives input selected from the group of comparisons of biological sequence data in addition to biological sequence database and query positions within a predetermined window of data and at least one scoring stage of the plurality of scoring stages receives input from at least one other scoring stage of the plurality of scoring stages, wherein the input is selected from the group consisting of scores of high-scoring segment pairs and endpoints of high-scoring segment pairs.

79. The circuit of claim 68, wherein the scoring module further comprises a threshold comparator.

80. The circuit of claim 79, wherein the threshold comparator obtains a pattern match of a predetermined length that includes at least one score and determines if the at least one score exceeds a predetermined threshold value and passes the pattern match downstream.

81. The circuit of claim 79, wherein the threshold comparator obtains a pattern match of a predetermined length and determines if a high scoring substring intersects a boundary of a predetermined window of data.

82. A method for performing biological sequence similarity searching, the method comprising:

processing a biological sequence data stream with a programmable logic device configured to include a pipeline that comprises a matching stage, the matching stage being configured to receive a data stream comprising a plurality of possible matches between a plurality of biological sequence data strings and a plurality of substrings of a query string; and

utilizing a ungapped extension prefilter stage located downstream from the matching stage in the pipeline, the ungapped extension prefilter stage being configured to shift through pattern matches between the biological sequence data strings and the plurality of substrings of a query string and provide a score so that only pattern matches that exceed a user defined score will pass downstream from the ungapped extension prefilter stage.

83. The method of claim 82, wherein the programmable logic device comprises an FPGA.

84. The method of claim 82, wherein the matching stage includes utilizing at least a portion of a first stage for BLAST and the ungapped extension prefilter stage includes utilizing at least a portion of a second stage for BLAST.

85. The method of claim 84, wherein the BLAST first stage is selected from the group consisting of a first stage for BLASTN, BLASTP, BLASTX, TBLASTN, and TBLASTX and the BLAST second stage is selected from the group consisting of a second stage for BLASTN, BLASTP, BLASTX, TBLASTN, and TBLASTX.

86. The method of claim 82, comprises utilizing a Bloom filter stage in the matching stage of the pipeline.

87. The method of claim 86, wherein the Bloom filter stage includes a plurality of Bloom filters.

88. The method of claim 86, further comprising utilizing a hashing stage downstream from the Bloom filter stage and mapping the possible matches to at least one position within the query string with the hashing stage.

89. The method of claim 88, further comprising utilizing a redundancy filter downstream from the hashing stage, with the redundancy filter being configured to receive data representative of possible matches from the hashing stage and further comprising removing possible matches that are redundant with previous possible matches within a selectable degree of redundancy.

90. The method of claim 82, wherein the ungapped extension prefilter stage comprises an extension controller, a window lookup module and a scoring module.

91. The method of claim 82, further comprising utilizing parameters selected from the group consisting of a match score, a mismatch score or a cutoff threshold with the ungapped extension prefilter stage.

92. The method of claim 82, wherein the ungapped extension prefilter stage comprises an extension controller.

93. The method of claim 92, wherein the extension controller comprises at least one of hardware, firmware and software.

94. The method of claim 92, further comprising receiving a plurality of possible pattern matches of a predetermined length between a plurality of biological sequence data strings and a plurality of substrings of a query string as at least one first input and receiving biological sequence data with at least one second input.

95. The method of claim 94, further comprising receiving commands for controlling parameters selected from the group consisting of a match score, a mismatch score or a cutoff threshold with the at least one second input.

96. The method of claim 90, further comprising parsing the data received by the at least one second input to demultiplex the shared command and the pattern matches of a predetermined length prior to submission into the window lookup module.

97. The method of claim 82, wherein the ungapped extension prefilter stage comprises a window lookup module.

98. The method of claim 97, further comprising fetching at least one substring of the biological sequence data and at least one substring of a query string to form a predefined window of biological data for analysis with the window lookup module.

99. The method of claim 97, further comprising:

receiving at least one substring of the biological sequence data in a database buffer with the window lookup module;

receiving at least one substring of a query string in a query buffer with the window lookup module;

receiving an offset for the at least one substring of the biological sequence data and an offset for the at least one substring of a query string that is utilized to calculate a beginning of a window;

moving the offset for the at least one substring of the biological sequence data and the offset for at least one substring of a query string with a plurality of buffer modules; and

creating at least one predefined window of biological data for analysis based on the at least one substring of the biological sequence data, the at least one substring of a query string, the offset for the at least one substring of the biological sequence data and the offset for at least one substring of a query string.

100. The method of claim 98, further comprising buffering the at least one substring of the biological sequence data and at least one substring of a query string on a plurality of BRAMS.

101. The method of claim 82, wherein the ungapped extension prefilter stage comprises a scoring module.

102. The method of claim 101, further comprising fetching biological data within a predefined window with the scoring module.

103. The method of claim 101, further utilizing at least one iteration of algorithm instructions with the scoring module.

104. The method of claim 101, wherein the scoring module further comprises a base comparator, a plurality of scoring stages and a threshold comparator.

105. The method of claim 101, wherein the scoring module further comprises a base comparator.

106. The method of claim 105, further comprising receiving at least one pair of a substring of the biological sequence data and a substring of a query string and comparing these values and obtaining at least one comparison score with the base comparator.

107. The method of claim 106, wherein the at least one comparison score includes a positive value for each matching pair and a negative score for each mismatching pair.

108. The method of claim 106, further comprising substituting the at least one comparison score from values located on a lookup table.

109. The method of claim 101, wherein the scoring module further comprises a plurality of scoring stages.

110. The method of claim 109, further comprising discarding at least one comparison score for each stage of the plurality of scoring stages.

111. The method of claim 109, further comprising receiving input selected from the group of comparisons of biological sequence data and biological sequence database and query positions within a predetermined window of data with at least one scoring stage of the plurality of scoring stages and further comprising receiving input is selected from the group consisting of scores of high-scoring segment pairs and endpoints of high-scoring segment pairs from at least one other scoring stage of the plurality of scoring stages.

112. The method of claim 101, wherein the scoring module further comprises a threshold comparator.

113. The method of claim 112, further comprising obtaining a pattern match of a predetermined length that includes at least one score and determines if the at least one score exceeds a predetermined threshold value with the threshold comparator and passing the pattern match downstream.

114. The method of claim 112, further comprising obtaining a pattern match of a predetermined length and determines if a high scoring substring intersects a boundary of a predetermined window of data with the threshold comparator.