Flexible seed extension for hash table genomic mapping

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

• one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations 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 and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed;
• 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;
• and
• based on determining that the extension table is to be accessed:
• accessing, by the mapping and aligning unit, the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record;
• and
• adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set.

A non-transitory, computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations 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 and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed;
• 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 an 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 to be accessed:
• accessing, by the mapping and aligning unit, the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record;
• and
• adding, by the mapping and aligning unit, the one or more matching reference sequence locations to a seed match set.

An integrated circuit for using a hash table to improve the mapping of sample reads to a reference sequence, the integrated circuit comprising multiple hardware logic gates that have been physically configured into one or more hardware digital logic circuits that realize functionality of a mapping and aligning unit, the integrated circuit comprising:

• one or more hardware logic circuits that execute 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;
• one or more hardware logic circuits that obtain 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;
• one or more hardware logic circuits that determine whether the response to the executed query includes (i) an extend record and (ii) an interval record, wherein the interval record identifies a contiguous set of reference sequence locations, stored in an extension table, that match the first seed;
• one or more hardware logic circuits that, based on a determination that the response to the executed query includes (i) an extend record and (ii) an interval record, determine 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;
• and
• one or more hardware logic circuits that, based on determining that the extension table is to be accessed:
• accessing the extension table to obtain the one or more matching reference sequence locations in the extension table that are referenced by the interval record, and adding the one or more matching reference sequence locations to a seed match set.