Back to results
US 2022/0093210 A1Published application
System and method for characterizing biological sequence data through a probabilistic data structure
AssigneeInvitae Corporation
InventorNicholas Boyd Greenfield
Life of this patent
Estimating the term…
Abstract
A system and method for resolving data through a probabilistic data structure can include initializing a B-field data structure, inserting a key-value element into the B-field data structure, selecting at least one key query, and looking up the value of a key lookup request through the B-field data structure.
Claims22
A method for resolving queries of a biological sequence data source comprising:
- allocating memory for a bit array;
- initializing bit values in the bit array;
- for a set of key-value mappings between a biological sequence k-mer and a characterization value, inserting each key-value mapping into a bit array, by:
- applying a set of hash operators to the biological sequence k-mer to obtain a first set of indexes, each index in the first set of indexes corresponding to a section of the bit array,
- encoding the characterization value to a binary bit mask of fixed-weight;
- bitwise ORing the binary bit mask with sections of the bit array corresponding to each index in the first set of indexes;
- receiving a biological sequence query comprising a set of overlapping biological sequence k-mers;
- selecting a set of overlapping biological sequence k-mers in the biological sequence query;
- and
- extracting a k-mer characterization for each biological sequence k-mer in the set of overlapping biological sequence k-mers, by:
- applying a set of hash operators to the biological sequence k-mer to select a second set of indexes,
- retrieving a set of binary masks, each binary mask in the set of binary masks corresponding to a location corresponding to an index in the second set of indexes,
- bitwise ANDing the set of binary mask into a combined bit mask,
- decoding the combined bit mask into a result characterization.
11 more elements
A method for storing and querying a key-value element comprising:
- initializing a bit array in memory of a computing platform;
- inserting a set of reference key-value elements into the bit array, wherein a reference key-value element maps a key to a value, by:
- applying a set of hash operators to the key to obtain a set of indexes;
- executing an encoding operation to convert the value to a fixed-weight binary bit mask;
- and
- bitwise ORing the binary bit mask at a set of locations of the bit array, the set of locations based on the set of indexes;
- selecting a query key;
- and
- extracting a result value of the query key from the bit array, by:
- applying the set of hash operators to the query key to obtain a second set of query indexes;
- collecting a set of bit masks from locations of the bit array based on the second set of query indexes;
- bitwise ANDing the set of bit masks into a combined bit mask;
- and
- applying a decoding operation to the combined bit mask to obtain a result value of the query key.
11 more elements
Dependencies are inferred from the claim text.