Method and Apparatus for Protein Sequence Alignment Using FPGA Devices

• US 20080086274A1
• Filed: 08/10/2007
• Published: 04/10/2008
• Est. Priority Date: 08/10/2006
• Status: Abandoned Application

• Current Assignee: Arpith Jacob, Brandon Harris, Jeremy Buhler, Joseph Lancaster, Roger Chamberlain
• Original Assignee: Arpith Jacob, Brandon Harris, Jeremy Buhler, Joseph Lancaster, Roger Chamberlain
• Inventors: Harris, Brandon, Buhler, Jeremy, Lancaster, Joseph, Jacob, Arpith, Chamberlain, Roger
• Application Number:
  US11/836,947
• Publication Number:
  US 20080086274A1
• Time in Patent Office: Days
• US Class Current: 702/19
• 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

Abstract

Disclosed herein is a hardware implementation for performing sequence alignment that preferably deploys a seed generation stage, an ungapped extension stage, and at least a portion of a gapped extension stage as a data processing pipeline on at least one hardware logic device. Hardware circuits for the seed generation stage, the ungapped extension stage, and the gapped extension stage are individually disclosed. In a preferred embodiment, the pipeline is arranged for performing BLASTP sequence alignment searching. Also, in a preferred embodiment, the at least one hardware logic device comprises at least one reconfigurable logic device such as an FPGA.

Claims

1. A data processing apparatus for sequence alignment searching, the apparatus comprising:

a first stage configured to (1) receive a bit stream that is representative of a database sequence and (2) process the bit stream to produce a plurality of seeds, each seed being indicative of a similarity between a substring of the database sequence and a substring of a query sequence;

a second stage configured to perform an ungapped extension analysis on the seeds generated by the first stage, thereby generating a plurality of high scoring pairs (HSPs); and

a third stage configured to perform a gapped extension analysis on the HSPs generated by the second stage, thereby determining whether any HSPs exist that will produce alignment of interest between the database sequence and the query sequence; and

wherein the first stage, the second stage, and at least a portion of the third stage are implemented as a data processing pipeline on at least one hardware logic device.

2. The apparatus of claim 1 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

3. The apparatus of claim 2 wherein the at least one reconfigurable logic device comprises at least one field programmable gate array (FPGA).

4. The apparatus of claim 1 wherein the first stage comprises a BLASTP seed generation stage, wherein the second stage comprises a BLASTP ungapped extension stage, and wherein the third stage comprises a BLASTP gapped extension stage.

5. The apparatus of claim 1 wherein the first stage, the second stage and all of the third stage is implemented as a data processing pipeline on at least one hardware logic device.

6. A method for sequence alignment searching, the method comprising:

generating a plurality of seeds from a database sequence and a query sequence;

performing an ungapped extension analysis on the generated seeds, thereby generating a plurality of high scoring pairs (HSPs);

performing a gapped extension analysis on the generated HSPs, thereby determining whether any HSPs will produce an alignment of interest between the database sequence and the query sequence; and

performing the seed generating step, ungapped extension analysis step and at least a portion of the gapped extension analysis step in a pipelined fashion on at least one hardware logic device.

7. The method of claim 6 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

8. The method of claim 7 wherein the database sequence corresponds to a protein biosequence.

9. The method of claim 8 wherein the query sequence corresponds to a protein biosequence.

10. The method of claim 9 further comprising performing the seed generating step, the ungapped extension analysis step and the gapped extension analysis step for BLASTP.

11. The method of claim 7 wherein the query sequence corresponds to a protein biosequence.

13. The method of claim 6 wherein the performing step comprises performing the seed generating step, ungapped extension analysis step all of the gapped extension analysis step in a pipelined fashion on at least one hardware logic device.

12. The method of 7 wherein the at least one reconfigurable logic device comprises at least one field programmable gate array (FPGA).

14. A hardware configured data processing apparatus for sequence alignment searching, the apparatus comprising at least one hardware logic device configured to (1) receive a bit stream that is representative of a database sequence, (2) process the bit stream to produce a plurality of seeds, each seed being indicative of a similarity between a substring of the database sequence and a substring of a query sequence, (3) perform an ungapped extension analysis on the generated seeds, thereby generating a plurality of high scoring pairs (HSPs), and (4) perform a gapped extension analysis on the generated HSPs, thereby determining whether any HSPs exist that will produce alignment of interest between the database sequence and the query sequence.

15. A computer-readable medium for sequence alignment searching, the computer-readable medium comprising:

a data structure comprising (1) first logic for a hardware logic device, the first logic configured to (a) receive a bit stream that is representative of a database sequence and (b) process the bit stream to produce a plurality of seeds, each seed being indicative of a similarity between a substring of the database sequence and a substring of a query sequence, (2) second logic for a hardware logic device, the second logic configured to perform an ungapped extension analysis on the generated seeds, thereby generating a plurality of high scoring pairs (HSPs), and (3) third logic for a hardware logic device, the third logic configured to perform a gapped extension analysis on the generated HSPs, thereby determining whether any HSPs exist that will produce alignment of interest between the database sequence and the query sequence, wherein the data structure is configured such that the first logic, the second logic, and the third logic will be implemented as a data processing pipeline on at least one hardware logic device, and wherein the data structure is resident on the computer-readable medium.

16. The computer-readable medium of claim 15 wherein the data structure comprises one selected from the group consisting of:

(1) high level source code that is machine-readable by a compiler to generate code level logic, (2) high level source code that is machine-readable by a synthesizer to generate gate level logic, (3) code level logic that is machine-readable by a synthesizer to generate gate level logic, (4) gate level logic that is machine-readable by a place and route tool to generate a configuration template for loading onto a hardware logic device, and (5) a configuration template for loading onto a hardware logic device.

17. A method of providing a data structure for conversion into a configuration template for configuring a hardware logic device, the method comprising:

providing a data structure that is convertible into a configuration template for loading onto a hardware logic device, the data structure comprising logic for a seed generation stage for a BLAST pipeline, an ungapped analysis stage for a BLAST pipeline, and a gapped analysis stage for a BLAST pipeline, and

providing a tool for use in a process of converting the data structure into the configuration template.

18. A method of converting a data structure to a new data structure, the method comprising:

accessing a first data structure that is convertible into a configuration template for loading onto a hardware logic device, the first data structure comprising logic for a seed generation stage for a BLAST pipeline, an ungapped analysis stage for a BLAST pipeline, and a gapped analysis stage for a BLAST pipeline, and

using at least one tool to convert the first data structure into a second data structure, the second data structure comprising one selected from the group consisting of (1) a new data structure that is also convertible into a configuration template for loading onto a hardware logic device, and (2) a configuration template for loading onto a hardware logic device.

19. An apparatus for sequence alignment searching to find a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the apparatus comprising:

a hit generator, the hit generator comprising (1) a memory configured as a lookup table and (2) a table lookup unit in communication with the memory;

wherein the lookup table is configured to store a plurality of hit identifiers, each hit identifier corresponding to a hit between a database substring and a query substring;

wherein the table lookup unit is configured to (1) receive a bit stream corresponding to a plurality of database substrings, and (2) for each received database substring, access the lookup table to retrieve therefrom each hit identifier corresponding to that database substring; and

wherein at least the table lookup unit is implemented on a hardware logic device.

20. The apparatus of claim 19 wherein the hardware logic device comprises a reconfigurable logic device.

21. The apparatus of claim 20 wherein each database substring comprises a database w-mer and wherein each query substring comprises a query w-mer, the database w-mers and the query w-mers comprising residue substrings of length w, the apparatus further comprising:

a w-mer feeder unit in communication with the hit generator, the w-mer feeder unit being configured to (1) receive and process a bitstream comprising at least a portion of the database sequence to thereby generate a plurality of database w-mers for delivery to the hit generator and (2) generate a database sequence pointer for each database w-mer that identifies a position within the database sequence for each database w-mer, wherein the w-mer feeder unit is implemented on the reconfigurable logic device.

22. The apparatus of claim 21 wherein the table lookup unit is further configured to index the lookup table by a value corresponding to each database w-mer, and wherein each hit identifier comprises a pointer stored in an address of the lookup table corresponding to that database w-mer, the pointer comprising a query sequence pointer to a position of a query w-mer in the query sequence that is deemed a match to that database w-mer.

23. The apparatus of claim 22 wherein the query w-mers in the query sequence that are deemed a match to a given database w-mer comprise a neighborhood of query w-mers.

24. The apparatus of claim 23 wherein the lookup table comprises a modular delta encoding of the hit identifiers.

25. The apparatus of claim 24 wherein the lookup table comprises a primary table and a duplicate table, the primary table being configured to store up to a preselected number of hit identifiers corresponding to a given w-mer, and the duplicate table being configured to store hit identifiers corresponding to a given w-mer wherein the number of hit identifiers exceeds the pre-selected number.

26. The apparatus of claim 24 wherein the hit generator further comprises a base conversion unit in communication with the w-mer feeder unit and the table lookup unit, the base conversion unit being configured to (1) receive the stream of database w-mers from the w-mer feeder unit, and (2) change the base of each database w-mer, thereby generating a plurality of base-converted database w-mers, and wherein the bitstream received by the table lookup unit comprises a bitstream of the base-converted database w-mers.

27. The apparatus of claim 26 further comprising a hit compute unit in communication with the table lookup unit, the hit compute unit being configured to (1) receive a stream of query sequence pointers from the table lookup unit, (2) decode the modular delta-encoded query sequence pointers, (3) output a stream of hits, each hit corresponding to a query sequence pointer paired with a database sequence pointer.

28. The apparatus of claim 20 wherein the memory comprises a memory that is not implemented on the reconfigurable logic device.

29. The apparatus of claim 28 wherein the memory comprises an SRAM memory device.

30. The apparatus of claim 20 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

31. A method for sequence alignment searching to find a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the method comprising:

maintaining a lookup table that stores a plurality of hit identifiers, each hit identifier corresponding to a hit between a database substring and a query substring;

receiving a bitstream comprising a plurality of database substrings;

for each received database substring, accessing the lookup table to retrieve therefrom each hit identifier corresponding to that database substring; and

wherein the receiving and accessing steps are performed by a hardware logic device.

32. The method of claim 31 wherein the hardware logic device comprises a reconfigurable logic device.

33. The method of claim 31 wherein the database sequence comprises a protein biosequence.

34. The method of claim 31 wherein the query sequence comprises a protein biosequence.

35. The method of claim 31 wherein the database sequence comprises a profile.

36. The method of claim 31 wherein the query sequence comprises a profile.

37. A computer-readable medium for sequence alignment searching to find a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the computer-readable medium comprising:

a data structure comprising logic for a table lookup unit for accessing a lookup table, the lookup table being configured to store a plurality of hit identifiers, each hit identifier corresponding to a hit between a database substring and a query substring, the table lookup unit being configured to (1) receive a bit stream corresponding to a plurality of database substrings, and (2) for each received database substring, access the lookup table to retrieve therefrom each hit identifier corresponding to that database substring, wherein the data structure is configured such that the table lookup unit will be implemented on a hardware logic device, and wherein the data structure is resident on the computer-readable medium.

38. The computer-readable medium of claim 37 wherein the data structure comprises one selected from the group consisting of:

(1) high level source code that is machine-readable by a compiler to generate code level logic, (2) high level source code that is machine-readable by a synthesizer to generate gate level logic, (3) code level logic that is machine-readable by a synthesizer to generate gate level logic, (4) gate level logic that is machine-readable by a place and route tool to generate a configuration template for loading onto a hardware logic device, and (5) a configuration template for loading onto a hardware logic device.

39. An apparatus for sequence alignment searching to find a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the apparatus comprising:

a word matching module configured to (1) receive a bitstream comprising a plurality of data substrings and (2) find a plurality of hits between the data substrings and a plurality of query substrings; and

a hit filtering module in communication with the word matching module, the hit filtering module configured to (1) receive a stream of hits from the word matching module and (2) filter the received hits based at least in part upon whether a plurality of hits are determined to be sufficiently close to each other in the database sequence; and

wherein the hit filtering module is implemented on a hardware logic device.

40. The apparatus of claim 39 wherein the hardware logic device comprises a reconfigurable logic device.

41. The apparatus of claim 40 wherein at least a portion of the word matching module is implemented on the reconfigurable logic device.

42. The apparatus of claim 41, wherein the word matching module is further configured to provide a stream of hits to the hit filtering module, wherein each hit is defined as a query sequence position identifier paired with a database sequence position identifier, and wherein the hit filtering module is configured to (1) compute a diagonal index from each hit'"'"'s query sequence position identifier and database sequence position identifier and (2) filter the hits at least partially on the basis of which hits share the same diagonal index.

43. The apparatus of claim 42 wherein the hit filtering module comprises a two hit module.

44. The apparatus of claim 43 wherein the two hit module is configured to maintain a hit if that hit includes a database sequence position identifier whose value is within a pre-selected distance from a value for a database sequence position identifier of a hit sharing the same diagonal index value.

45. The apparatus of claim 44 wherein the two hit module comprises a BRAM memory unit for storing each hit'"'"'s database sequence position identifier value indexed by that hit'"'"'s diagonal index value.

46. The apparatus of claim 42 further comprising a plurality of the hit filtering modules and a switch in communication with the word matching module and the plurality of hit filtering modules, wherein the switch is configured to selectively route each hit from the word matching module to one of the plurality of the hit filtering modules.

47. The apparatus of claim 42 wherein the switch is configured to (1) associate each hit filtering module with at least one diagonal index value, and (2) route each hit to a hit filtering module based on which hit filtering module is associated with the diagonal index value for that hit.

48. The apparatus of claim 47 wherein the switch is configured to modulo division route the hits to the hit filtering modules.

49. The apparatus of claim 48 further comprising a plurality of the word matching modules, a plurality of the switches, and a plurality of buffered multiplexers, each switch being in communication with a word matching module and each of the buffered multiplexers, each buffered multiplexer being in communication with a hit filtering module, and wherein each buffered multiplexer is configured to multiplex hits that are destined for the hit filtering module in communication therewith and that are received from the plurality of switches.

50. The apparatus of claim 49 wherein each hit maintained by the hit filtering module comprises a seed, the apparatus further comprising a seed reduction module that is configured to multiplex the seeds produced by the plurality of hit filtering modules into a single stream of seeds.

51. The apparatus of claim 46 further comprising a plurality of ungapped extension analysis circuits implemented on the hardware logic device, wherein each hit filtering module is configured to route its hits to at least one of the plurality of ungapped extension analysis circuits.

52. A method for sequence alignment searching to find a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the method comprising:

receiving a bitstream comprising a plurality of data substrings;

finding a plurality of hits between the data substrings and a plurality of query substrings; and

filtering the received hits based at least in part upon whether a plurality of hits are determined to be sufficiently close to each other in the database sequence; and

wherein the filtering step is performed by a hardware logic device.

53. The method of claim 52 wherein the hardware logic device comprises a reconfigurable logic device.

54. The method of claim 52 wherein the database sequence comprises a protein biosequence.

55. The method of claim 52 wherein the query sequence comprises a protein biosequence.

56. The method of claim 52 wherein the database sequence comprises a profile.

57. The method of claim 52 wherein the query sequence comprises a profile.

58. A computer-readable medium for sequence alignment searching to find a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the computer-readable medium comprising:

a data structure comprising (1) first logic for a word matching module configured to (a) receive a bitstream comprising a plurality of data substrings and (b) find a plurality of hits between the data substrings and a plurality of query substrings, and (2) second logic for a hit filtering module in communication with the word matching module, the hit filtering module configured to (a) receive a stream of hits from the word matching module and (b) filter the received hits based at least in part upon whether a plurality of hits are determined to be sufficiently close to each other in the database sequence, wherein the data structure is configured such that the word matching module and the hit filtering module will be implemented on a hardware logic device as a data processing pipeline, and wherein the data structure is resident on the computer-readable medium.

59. The computer-readable medium of claim 58 wherein the data structure comprises one selected from the group consisting of:

(1) high level source code that is machine-readable by a compiler to generate code level logic, (2) high level source code that is machine-readable by a synthesizer to generate gate level logic, (3) code level logic that is machine-readable by a synthesizer to generate gate level logic, (4) gate level logic that is machine-readable by a place and route tool to generate a configuration template for loading onto a hardware logic device, and (5) a configuration template for loading onto a hardware logic device.

60. A method for populating a lookup table for use in finding hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the method comprising:

for each of a plurality of query substrings, determining each position in the query sequence therefor;

modular delta encoding the determined positions; and

storing the modular delta encoded positions in a lookup table that is addressed at least partially by a plurality of item substrings corresponding to all possible combinations of items having a length equal to the query substrings.

61. The method of claim 60 wherein the lookup table comprises a primary table and a duplicate table, wherein the storing step comprises:

for each query substring having a number of modular delta encoded positions that is less than or equal to a pre-selected value, storing those modular delta encoded positions in the primary table at an address corresponding to that query substring; and

for each query substring having a number of modular delta encoded positions that exceeds the pre-selected value, (1) storing those modular delta encoded positions in the duplicate table and (2) storing, at an address in the primary table corresponding to that query substring, data that identifies where in the duplicate table that those modular delta encoded positions can be found.

62. The method of claim 61 further comprising using a bit stored in each address of the primary table as a bit signifying whether the modular delta encoded positions for the query substring for that address are found in the primary table or the duplicate table.

63. The method of claim 61 further comprising:

for each query substring, determining a plurality of query substrings that are within a neighborhood of that query substring; and

wherein the positions determined by the position determining step also include the positions of the query substrings that were determined to be in the neighborhood of that query substring.

64. The method of claim 60 further comprising:

base converting the query substrings prior to the modular delta encoding step to reduce the amount of memory required for the lookup table.

65. The method of claim 60 further comprising:

performing the determining, encoding and storing steps for at least one query sequence prior to performing a similarity search between the database sequence and the at least one query sequence using a hardware logic device that is configured to access the lookup table as parts of the similarity search.

66. The method of claim 60 wherein the database sequence comprises a protein biosequence.

67. The method of claim 60 wherein the query sequence comprises a protein biosequence.

68. A computer readable medium for populating a lookup table for use in finding hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the computer readable medium comprising:

a code segment executable by a processor for, for each of a plurality of query substrings, determining each position in the query sequence therefor;

a code segment executable by a processor for modular delta encoding the determined positions; and

a code segment executable by a processor for storing the modular delta encoded positions in a lookup table that is addressed at least partially by a plurality of item substrings corresponding to all possible combinations of items having a length equal to the query substrings.

69. An apparatus for sequence alignment searching for finding pairs of interest corresponding to a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the apparatus comprising:

a module for ungapped extension analysis, the module being configured to (1) receive a stream of hits between a plurality of database substrings and a plurality of query substrings, and (2) identify which hits are high scoring pairs (HSPs) on the basis of a scoring matrix; and

wherein the ungapped extension analysis module is implemented on at least one hardware logic device.

70. The apparatus of claim 69 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

71. The apparatus of claim 70 wherein the ungapped extension analysis module comprises a BLASTP ungapped extension analysis module.

72. The apparatus of claim 71 wherein the scoring matrix comprises a BLOSUM-62 scoring matrix.

73. The apparatus of claim 72 wherein the scoring matrix is stored in at least one BRAM unit that is implemented on the at least one reconfigurable logic device.

74. The apparatus of claim 70 wherein the at least one reconfigurable logic device comprises at least one field programmable gate array (FPGA).

75. A method for sequence alignment searching to find pairs of interest corresponding to a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the method comprising:

receiving a stream of hits between a plurality of database substrings and a plurality of query substrings;

performing an ungapped extension analysis on the received hits using a scoring matrix to identify which hits are high scoring pairs (HSPs); and

wherein the receiving step and the performing step are performed by at least one hardware logic device.

76. The method of claim 75 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

77. The method of claim 75 wherein the database sequence comprises a protein biosequence.

78. The method of claim 75 wherein the query sequence comprises a protein biosequence.

79. The method of claim 75 wherein the database sequence comprises a profile.

80. The method of claim 75 wherein the query sequence comprises a profile.

81. A computer-readable medium for sequence alignment searching for finding pairs of interest corresponding to a plurality of hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the computer-readable medium comprising:

a data structure comprising logic for a module for ungapped extension analysis, the module being configured to (1) receive a stream of hits between a plurality of database substrings and a plurality of query substrings, and (2) identify which hits are high scoring pairs (HSPs) on the basis of a scoring matrix, wherein the data structure is configured such that the ungapped extension analysis module will be implemented on a hardware logic device, and wherein the data structure is resident on the computer-readable medium.

82. The computer-readable medium of claim 81 wherein the data structure comprises one selected from the group consisting of:

(1) high level source code that is machine-readable by a compiler to generate code level logic, (2) high level source code that is machine-readable by a synthesizer to generate gate level logic, (3) code level logic that is machine-readable by a synthesizer to generate gate level logic, (4) gate level logic that is machine-readable by a place and route tool to generate a configuration template for loading onto a hardware logic device, and (5) a configuration template for loading onto a hardware logic device.

83. An apparatus for sequence alignment searching using hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the apparatus comprising:

a module for gapped extension analysis, the module being configured to (1) receive a stream of hits between a plurality of database substrings and a plurality of query substrings, and (2) identify the hits in the hit stream for which there exists an alignment of interest that exceeds a threshold using a banded Smith-Waterman algorithm;

wherein the gapped extension analysis module is implemented on at least one hardware logic device.

84. The apparatus of claim 83 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

85. The apparatus of claim 84 wherein the gapped extension analysis module comprises a BLASTP gapped extension analysis module.

86. The apparatus of claim 84 wherein the banded Smith-Waterman algorithm comprises a seeded and banded Smith-Waterman algorithm.

87. The apparatus of claim 84 wherein the at least one reconfigurable logic device comprises at least one field programmable gate array.

88. A method for sequence alignment searching using hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the method comprising:

receiving a stream of hits between a plurality of database substrings and a plurality of query substrings; and

performing a banded Smith-Waterman gapped extension analysis on the received hits to identify whether any hits will produce an alignment that exceeds a threshold within a band geometry; and

wherein the receiving step and the performing step are performed by at least one hardware logic device.

89. The method of claim 88 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

90. A computer-readable medium for sequence alignment searching using hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the computer-readable medium comprising:

a data structure comprising logic for a module for gapped extension analysis, the module being configured to (1) receive a stream of hits between a plurality of database substrings and a plurality of query substrings, and (2) identify the hits in the hit stream for which there exists an alignment of interest that exceeds a threshold using at least one selected from the group consisting of a banded Smith-Waterman algorithm and a seeded Smith-Waterman algorithm, wherein the data structure is configured such that the gapped extension analysis module will be implemented on a hardware logic device, and wherein the data structure is resident on the computer-readable medium.

91. The computer-readable medium of claim 90 wherein the data structure comprises one selected from the group consisting of:

(1) high level source code that is machine-readable by a compiler to generate code level logic, (2) high level source code that is machine-readable by a synthesizer to generate gate level logic, (3) code level logic that is machine-readable by a synthesizer to generate gate level logic, (4) gate level logic that is machine-readable by a place and route tool to generate a configuration template for loading onto a hardware logic device, and (5) a configuration template for loading onto a hardware logic device.

92. An apparatus for sequence alignment searching using hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the apparatus comprising:

a module for gapped extension analysis, the module being configured to (1) receive a stream of hits between a plurality of database substrings and a plurality of query substrings, and (2) identify hits within the hit stream for which there exists an alignment that exceeds a threshold using a seeded Smith-Waterman algorithm;

wherein the gapped extension analysis module is implemented on at least one hardware logic device.

93. The apparatus of claim 92 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

94. A method for sequence alignment searching using hits between a plurality of database substrings and a plurality of query substrings, each database substring corresponding to a plurality of items of a database sequence and each query substring corresponding to a plurality of items of a query sequence, the method comprising:

receiving a stream of hits between a plurality of database substrings and a plurality of query substrings; and

performing a gapped extension analysis on the received hits using a seeded Smith-Waterman algorithm to identify whether any hits correspond to an alignment of interest; and

wherein the receiving step and the performing step are performed by at least one hardware logic device.

95. The method of claim 94 wherein the at least one hardware logic device comprises at least one reconfigurable logic device.

96. A computer-implemented method comprising:

storing a first template that defines a first sequence analysis algorithm;

storing a second template that defines a second sequence analysis algorithm;

selecting one of the stored templates; and

loading the selected template onto a reconfigurable logic device to thereby configure that reconfigurable logic device to perform a sequence analysis corresponding to the loaded template when a database sequence is streamed through the reconfigurable logic device.

97. The method of claim 96 wherein the first sequence analysis algorithm comprises a BLASTP similarity searching operation and wherein the second sequence analysis algorithm comprises a BLASTN similarity searching operation.

98. A computer-implemented method comprising:

selecting whether a first sequence analysis algorithm or a second sequence analysis algorithm is to be performed;

defining a template for the selected one of the first and second sequence analysis algorithms; and

loading the defined template onto a reconfigurable logic device to thereby configure that reconfigurable logic device to perform a sequence analysis corresponding to the loaded template when a database sequence is streamed through the reconfigurable logic device.

99. The method of claim 98 wherein the first sequence analysis algorithm comprises a BLASTN similarity search and wherein the second sequence analysis algorithm comprises a BLASTP similarity search.