System and method for characterizing biological sequence data through a probabilistic data structure

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.

I claim: 
     
         1 . 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. 
   
     
     
         2 . The method of  claim 1 ,
 wherein inserting each key-value mapping into a bit array comprises:
 detecting an indeterminate error scenario for an key-value mapping; and, 
 in response to an indeterminate error scenario, inserting the key-value mapping in a secondary array mode; and 
   wherein extracting a k-mer characterization of each of the biological sequence k-mers comprises: in response to detection of an indeterminate error scenario for a biological sequence k-mer in the first bit array, extracting a k-mer characterization of the biological sequence k-mer in the secondary array mode.   
     
     
         3 . The method of  claim 2 , where initializing bit values in the bit array further comprises initializing a set of secondary bit arrays in distinct memory locations of a computing platform. 
     
     
         4 . The method of  claim 2 , wherein inserting the key-value mapping in the secondary bit array mode comprises: applying a secondary set of hash operators to the biological sequence k-mer to obtain a second set of indexes; and bitwise ORing the binary bit mask at a set of locations of the secondary bit array, the set of locations based on the second set of indexes, and the secondary bit array overlapping the bit array in memory. 
     
     
         5 . The method of  claim 1 , further comprising:
 identifying a minimizing bioinformatics m-mer for biological sequence k-mers in the set of key-value mappings;   wherein obtaining a set of indexes when inserting comprises applying a first subset of hash operators to the biological sequence k-mer to obtain a first subset of indexes for the set of indexes and applying a second subset of hash operators to the minimizing bioinformatics m-mer to obtain a second subset of indexes for the set of indexes;   identifying a minimizing bioinformatics m-mer in a biological sequence k-mer of the set of overlapping biological sequence k-mers; and   wherein obtaining the set of query indexes during lookup comprises applying a first subset of hash operators to the biological sequence fragment to obtain a first subset of indexes for the set of query indexes and applying a second subset of hash operators to the minimizing bioinformatics m-mer of the biological sequence query key to obtain a second subset of indexes for the second set of query indexes.   
     
     
         6 . The method of  claim 1 , wherein allocating memory for the bit array comprises allocating memory for the bit array in an internet-accessible distributed computing environment. 
     
     
         7 . The method of  claim 1 , wherein applying the set of hash operators to the biological sequence k-mer comprises applying the set of hash operators to a nucleotide sequence k-mer. 
     
     
         8 . The method of  claim 1 , wherein applying the set of hash operators to the biological sequence k-mer comprises applying the set of hash operators to a protein sequence k-mer. 
     
     
         9 . The method of  claim 1 , further comprising generating a characterization report based on a set of result k-mer characterizations, which comprises generating a summary of biological classifications identified in the result k-mer characterizations of the set of the biological sequence k-mers. 
     
     
         10 . 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 . The method of  claim 10 , further comprising: detecting an indeterminate error scenario of the bit array in response to inserting a key-value element into the bit array; and, in response to detecting an indeterminate error scenario, inserting the key-value element into a secondary bit array. 
     
     
         12 . The method of  claim 11 , wherein initializing the bit array in memory of the computing platform further comprises initializing a set of secondary bit arrays in distinct memory locations of the computing platform. 
     
     
         13 . The method of  claim 11 , wherein inserting the key-value element into the secondary bit array comprises: applying a secondary set of hash operators to the key to obtain a second set of indexes; and bitwise ORing the binary bit mask at a set of locations of the secondary bit array, the set of locations based on the second set of indexes, and the secondary bit array overlapping the bit array in memory. 
     
     
         14 . The method of  claim 11 , further comprising: detecting a second indeterminate error scenario of the secondary bit array in response to inserting the key-value element into the secondary bit array; and, in response to detecting the second indeterminate error scenario, inserting the key-value element into a second secondary bit array. 
     
     
         15 . The method of  claim 10 , further comprising identifying a minimized key for a set of keys in the set of key-value elements; and wherein obtaining the set of indexes comprises obtaining a first subset of indexes for the set of indexes by applying a first subset of hash operators to the key and obtaining a second subset of indexes for the set of indexes by applying a second subset of hash operators to the minimized key. 
     
     
         16 . The method of  claim 15 , wherein obtaining the second set of query indexes comprises obtaining a first subset of indexes for the second set of query indexes by applying a first subset of hash operators to the key and obtaining a second subset of indexes for the second set of query indexes by applying a second subset of hash operators to the minimized key of the query key. 
     
     
         17 . The method of  claim 10 , wherein inserting the set of reference key-value elements in the bit array comprises inserting the set of reference key-value elements in the bit array at a first time instance; and further comprising inserting a second set of reference key-value elements in the bit array at a second time instance succeeding the first time instance. 
     
     
         18 . The method of  claim 10 , further comprising setting configuration properties of insertion operators, look up operators, and the bit array, which comprises setting a maximum false positive rate, setting an expected number of key-value elements stored through the bit array, setting a maximum size of the set of values, setting bit mask weight, and setting a bit mask size. 
     
     
         19 . The method of  claim 10 , wherein inserting the set of reference key-value elements into the bit array and extracting a value of the query key from the bit array comprise complimentary operations that translate between an integer value and a value-associated bit pattern of a set size and set weight. 
     
     
         20 . The method of  claim 10 , wherein initializing the bit array in memory of the computing platform comprises initializing the bit array in memory of the computing platform hosted in an internet-accessible distributed computing environment. 
     
     
         21 . The method of  claim 20 , wherein initializing the bit array in memory of the computing platform comprises sharding the bit array across a set of computing resources in the distributed computing environment. 
     
     
         22 . The method of  claim 10 , wherein a reference key-value element maps a biological sequence fragment key to a biological characterization value.