Data structures and operations for searching, computing, and indexing in DNA-based data storage
The present disclosure is directed to enabling search and extraction of data stored in DNA with optimized data structures and functions. Accordingly, systems and methods are provided herein for performing certain functions on data stored in nucleic acid molecules. The present disclosure covers at least the following areas of interest: (1) data structures to provide efficient access and search of information stored in nucleic acid molecules, (2) accurate and quick reading of information stored in nucleic acid molecules, (3) targeted approaches to accessing subsets of information stored in nucleic acid molecules, (4) a rank function that determines a count of particular bit or symbol value in a set of information stored in nucleic acid molecules, (5) functions including counting, locating, and extracting occurrences of a specific pattern in a message of information stored in nucleic acid molecules, and (6) an if-then-else operation to sort data stored in nucleic acid molecules.
1. A method for obtaining a rank of a particular symbol value at a particular position in a string of symbols, each symbol having a symbol value and a symbol position, from digital information stored in a pool of nucleic acid molecules, the method comprising:
(a) obtaining a first pool of identifier nucleic acid molecules representative of the string of symbols, the pool having powder, liquid, or solid form, each identifier nucleic acid molecule in the first pool comprising component nucleic acid molecules, at least a portion of which are configured to bind to one or more probes;
(b) obtaining a second pool of identifier nucleic acid molecules representative of a string of counter symbols that is derived from the string of symbols, each counter symbol representing a running count of the particular symbol value in every w symbols of the string of symbols;
(c) obtaining a first count by accessing the second pool in (b) with a second series of probes to target at least the identifier nucleic acid molecules within the second pool that represent a corresponding counter symbol that indicates the running count of the particular symbol value for either (1) all blocks of w symbols preceding the particular position, or (2) all blocks of w symbols preceding the particular position and including the block of w symbols that includes the particular position;
(d) obtaining a second count by accessing the first pool in (a) with a first series of probes to target one or more distinct identifier nucleic acid molecules within the first pool that either (1) represents symbols not counted in (c) and preceding or including the particular position, or (2) represents symbols that were counted in (c) but that do not precede or include the particular position; and
(e) obtaining the rank of the particular symbol value at the particular position in the string of symbols from the first count and the second count.
2. The method of claim 1 , wherein the identifier nucleic acid molecules in the first pool represent a string of bits that map to the strings of symbols, such that the presence of an identifier nucleic acid molecules represents a particular symbol value at the symbol position.
3. The method of claim 1 , wherein when the first count in (c) represents all blocks of w symbols preceding the particular position, the first series of probes in (d) targets one or more distinct identifier nucleic acid molecules within the first pool that represents symbols not counted in (c) and preceding or including the particular position, and the rank of the particular symbol value at the particular position in the string of symbols is obtained by summing the first and second counts in (e).
4. The method of claim 1 , wherein when the first count in (c) represents all blocks of w symbols preceding the particular position and including the block of w symbols that includes the particular position, the first series of probes targets one or more distinct identifier nucleic acid molecules within the first pool that represents symbols counted in (c) but that do not precede or include the particular position, and the rank of the particular symbol value at the particular position in the string of symbols is obtained by subtracting the second count from the first count in (e).
5. The method of claim 1 , wherein the first count is obtained by reading the counter symbol value corresponding to the targeted identifier nucleic acid molecules in (c); and wherein the second count is obtained by reading the targeted identifier nucleic acid molecules from (d).
6. The method of claim 1 , wherein the presence of corresponding identifier nucleic acid molecules in the first pool indicates a first symbol value, and the absence of corresponding identifier nucleic acid molecules in the first pool indicates a second symbol value.
7. The method of claim 6 , wherein the string of symbols has length n, and the counter symbols are represented by b bits, where b is the ceiling of log 2 (n+1).
8. The method of claim 7 , wherein the string of counter symbols includes a ceiling of n divided by w counter symbols, and is represented by a string of counter bits having length corresponding to b multiplied by the ceiling of n divided by w.
9. The method of claim 1 , wherein if the particular position is within the first block of w symbols, the running count preceding the first block of w symbols is zero.
10. The method of claim 9 , wherein if the particular position is not within the first block of w symbols, the counter symbol of all blocks of w symbols preceding the particular position represents the number of occurrences of the particular symbol value within positions ranging from 0 to w*B(x)−1 of the string of symbols, where 0 is the first position of the string of symbols, and where x corresponds to the particular position in the string of symbols and B(x) is the floor of x divided by w.
11. The method of claim 10 , wherein the targeted identifier nucleic acid molecules within the second pool in (c) are within the range defined by positions b*B(x) and b*(B(x)+1)−1, where a position of 0 corresponds to the first position in the string of symbols.
12. The method of claim 1 , wherein the second count corresponds to a number of occurrences of the particular symbol value within the range of positions w*B(x) to x of the string of symbols, where x corresponds to the particular position in the string of symbols where position 0 is the first position, and B(x) is the floor of x divided by w.
13. The method of claim 1 , wherein w is set such that the length of bits to represent w symbols of the string of symbols is equivalent to the length of bits, b, to represent the counter symbols.
14. The method of claim 1 , wherein w is set to the value of one.
15. The method of claim 14 , wherein the first count is obtained by targeting identifier nucleic acid molecules in (c) that represent the counter symbol corresponding to the blocks of w symbols including the particular position, wherein the rank is equivalent to the first count, and wherein step (d) is not executed.
16. The method of claim 1 , wherein blocks of w symbols in the string of symbols are mapped to blocks of contiguously ordered identifier nucleic acid molecules in the first pool of identifier nucleic acid molecules.
17. The method of claim 16 , wherein the symbols in the string of symbols are bits, and each bit maps to an identifier nucleic acid molecule such that the presence or absence of said identifier in the first pool of identifier nucleic acid molecules signifies the value of the bit.
18. The method of claim 17 , wherein fixed length substrings of the string of symbols are mapped to codewords that comprise a fixed number of unique identifier nucleic acid molecules out of a fixed number of possible unique identifier nucleic acid molecules.
19. The method of claim 1 , wherein the string of symbols represents a string of bits.
20. The method of claim 19 , wherein each symbol of the string of symbols corresponds to a fixed number of bits.
21. The method of claim 19 , wherein different second pools of identifier nucleic acid molecules in (b) represent different strings of counter symbols that count the number of instances of specific symbol values, each different string of counter symbols counting instances of a corresponding specific symbol value.