Hardware Acceleration of Short Read Mapping for Genomic and Other Types of Analyses

A method for acceleration in a system of short read mapping to a reference sequence for proteomic analysis, the system having at least one host computing system, one or more field programmable gate arrays, and one or more memory circuits, the method comprising:

• using the one or more field programmable gate arrays, selecting a short read from a plurality of short reads, each short read of the plurality of short reads comprising a protein sequence;
• using the one or more field programmable gate arrays, extracting a plurality of seeds from the selected short read, each seed of the plurality of seeds comprising a subsequence of the selected short read;
• using the one or more field programmable gate arrays, for each seed of the plurality of seeds, determining at least one candidate alignment location in the reference sequence to form a plurality of candidate alignment locations;
• using the one or more field programmable gate arrays, for each candidate alignment location of the plurality of candidate alignment locations, determining a likelihood of the selected short read matching the reference sequence in a vicinity of the candidate alignment location;
• and
• using the one or more field programmable gate arrays, selecting one or more candidate alignment locations, of the plurality of candidate alignment locations, having a currently greater likelihood of the selected short read matching the reference sequence.

A system for acceleration of short read mapping to a reference sequence for proteomic analysis, the system coupled to a host computing system, the system comprising:

• one or more memory circuits configured to store a plurality of short reads and a reference sequence, each short read of the plurality of short reads comprising a protein sequence, and further configured to store a reference index partitioned over the one or more memory circuits to form a plurality of reference index partitions;
• and
• one or more field programmable gate arrays coupled to the one or more memory circuits, the one or more field programmable gate arrays configured to select a short read from the plurality of short reads;
• to extract a plurality of seeds from the selected short read, each seed of the plurality of seeds comprising a subsequence of the selected short read;
• to hash a selected seed, of the plurality of seeds, and use the hashed seed to access at least one reference index partition of the plurality of reference index partitions to determine at least one candidate alignment location in the reference sequence, for each seed of the plurality of seeds, to form a plurality of candidate alignment locations;
• for each candidate alignment location of the plurality of candidate alignment locations, to determine a likelihood of the selected short read matching the reference sequence in a vicinity of the candidate alignment location;
• and to select one or more candidate alignment locations, of the plurality of candidate alignment locations, having a currently greater likelihood of the selected short read matching the reference sequence.

The system of claim 33, wherein the host computing system is configured to create the reference index;

• and wherein the host computing system is further configured to determine all <seed, location>tuples in the reference sequence to form a plurality of <seed, location>tuples;
• to sort and eliminate redundant tuples from the plurality of <seed, location>tuples;
• for each seed of the plurality of seeds, to generate a forward sequence and a reverse complement sequence and determine which of the forward sequence or the reverse complement sequence is lexicographically smaller;
• for each seed of the plurality of seeds, to hash the lexicographically smaller sequence to produce a hash result;
• and for each seed of the plurality of seeds, to use the hash result as the hashed seed for the reference index;
• and wherein the host computing system is further configured to create a pointer table, each entry of the pointer table comprising a first predetermined number of most significant bits of a selected hashed seed and a corresponding pointer;
• and create a candidate alignment location table, each entry of the candidate alignment location table comprising a second predetermined number of least significant bits of the selected hashed seed and a corresponding candidate alignment location;
• and wherein the host computing system is further configured to filter the plurality of candidate alignment locations to eliminate any redundant candidate alignment locations. 39 (New). The system of claim 38, wherein the one or more field programmable gate arrays are further configured to determine the vicinity of the candidate alignment location as a sequence beginning at the start of the candidate alignment location minus a predetermined offset and extending through the end of the candidate alignment location plus a length of the selected short read and the predetermined offset.

A system for acceleration of short read mapping to a reference sequence for proteomic analysis, the system coupled to a host computing system, the system comprising:

• one or more memory circuits configured to store a plurality of short reads and a reference sequence divided into a plurality of reference blocks, each reference block having a size corresponding to a single read from the one or more memory circuits;
• and further configured to store a reference index, each short read comprising a protein sequence, the reference index comprising a pointer table and a candidate alignment location table;
• and
• one or more field programmable gate arrays coupled to the one or more memory circuits, the one or more field programmable gate arrays configured to select a short read from the plurality of short reads;
• to extract a plurality of seeds from the selected short read, each seed of the plurality of seeds comprising a genetic subsequence of the selected short read;
• for each seed of the plurality of seeds, to generate a forward sequence and a reverse complement sequence for a selected seed of the plurality of seeds and determine which of the forward sequence or the reverse complement sequence is lexicographically smaller;
• to hash the lexicographically smaller sequence to produce a hash result;
• to use the hash result to access the reference index to determine a candidate alignment location in the reference sequence to form a plurality of candidate alignment locations;
• for each selected candidate alignment location of the plurality of candidate alignment locations, to perform string matching to determine a likelihood of the short read matching the reference sequence in a vicinity of the selected candidate alignment location;
• and to select a candidate alignment location, of the plurality of candidate alignment locations, having a currently greatest likelihood of the short read matching the reference sequence.