Flexible seed extension for hash table genomic mapping

A method for using a hash table for mapping of sample reads to a reference sequence, the method comprising:

• executing, by a mapping and aligning unit, a query of a hash table, the query including a first seed, wherein the first seed includes a subset of nucleotides that were obtained from a particular read of the sample reads;
• obtaining, by the mapping and aligning unit, a response to the executed query that includes information stored by a location of the hash table that is determined to be responsive to the query;
• determining, by the mapping and aligning unit, whether the response to the executed query includes (i) an extend record (ii) an interval record, or (iii) one or more matching reference sequence locations, wherein the interval record references one or more locations, in an extension table, that include data describing reference sequence locations that match the first seed of the query;
• based on determining, by the mapping and aligning unit, that the response to the executed query includes (i) an extend record and (ii) an interval record:
• determining, by the mapping and aligning unit, whether the extension table is to be accessed to obtain one or more matching reference sequence locations in the extension table that are referenced by the interval record;
• based on determining that the extension table is not to be accessed:
• determining, by the mapping and aligning unit, whether to store the first information describing the interval record in a memory device as information describing a candidate best interval, wherein the determining comprises:
• determining, by the mapping and aligning unit, that there is not prior information describing an interval record as a candidate best interval for the particular read;
• and
• storing, by the mapping and aligning unit, the first information describing the interval record in the memory device as information describing a candidate best interval;
• generating, by the mapping and aligning unit, a first extended seed that is an extension of the first seed using the extend record;
• generating, by the mapping and aligning unit, a subsequent hash query that includes the first extended seed;
• and
• executing, by the mapping and aligning unit, the subsequent hash query of the hash table.