Reference marks storing embedded oligo index in DNA data storage
Example systems and methods for embedding an oligo index in a series of reference marks along the oligo for DNA data storage are described. A data unit may be encoded in oligos that include reference marks at predetermined intervals along the length of each oligo that encode the oligo index, generally in multiple copies encoded with varying symmetries. During decoding, the reference marks may be analyzed through multiple correlation matrices to determine a most likely set of values for the oligo index. In some configurations, the same reference marks may be processed through another correlation matrix to determine and correct insertions and deletions based on multiple copies of the oligo, as identified by the decoded oligo indices in those copies.
1 . A system, comprising:
an encoder configured to:
determine an oligo for encoding a data unit, wherein the oligo encodes a number of symbols corresponding to user data in the data unit;
insert a plurality of reference marks at a predetermined interval along a length of the oligo, wherein:
at least one set of reference marks in the plurality of reference marks encodes an oligo index; and
the predetermined interval equals a fixed data length between sequential reference marks; and
output write data for the oligo for synthesis of the oligo.
2 . The system of claim 1 , wherein the predetermined interval of the plurality of reference marks corresponds to a single base pair between sequential reference marks.
3 . The system of claim 1 , wherein the oligo index comprises:
an oligo address; and
a cyclic redundancy check code.
4 . The system of claim 1 , wherein the plurality of reference marks comprises a plurality of copies of the oligo index.
5 . The system of claim 4 , wherein:
each copy of the oligo index comprises a different set of reference marks of the at least one set of reference marks; and
at least two copies of the oligo index comprise different translations of the oligo index that order the corresponding sets of reference marks in different translation orders.
6 . The system of claim 5 , wherein:
each copy of the oligo index:
occupies a predetermined set of positions in the plurality of reference marks; and
has a known translation order for that predetermined set of positions and corresponding set of reference marks; and
the different translation orders are selected from:
mirror symmetry; and
translational symmetry using circular offset values less than a length of the oligo index.
7 . The system of claim 6 , wherein:
the plurality of reference marks comprises a reference number of base pairs in the oligo;
the reference number of base pairs is a multiple of the length of the oligo index;
the multiple is at least equal to a number of the plurality of copies; and
the number of the plurality of copies is at least four.
8 . The system of claim 5 , wherein the different sets of reference marks of the at least two copies are interleaved along the length of the oligo index.
9 . A system comprising:
an index decoder configured to:
receive read data determined from sequencing an oligo, wherein:
the oligo encodes:
a number of symbols corresponding to user data in a data unit; and
a plurality of reference marks at a predetermined interval along a length of the oligo;
at least one set of reference marks in the plurality of reference marks encodes an oligo index; and
the predetermined interval equals a fixed data length between sequential reference marks;
determine, from the read data, a convolutional matrix for the oligo, wherein each column of the convolutional matrix corresponds to a base pair offset of the read data for the oligo;
determine, from the read data, a first reference matrix based on a first sequence of reference positions at an encoded frequency of the plurality of reference marks;
determine, from the read data, a second reference matrix based on a second sequence of reference positions at the encoded frequency of the plurality of reference marks;
determine a first correlation matrix based on a comparison of the convolutional matrix to the first reference matrix;
determine a second correlation matrix based on a comparison of the convolutional matrix and the second reference matrix;
determine a most likely path through a combination of the first correlation matrix and the second correlation matrix based on:
a series of probabilities of moving between corresponding rows in the first correlation matrix and the second correlation matrix; and
loop decoding for different symmetries of a plurality of copies of the oligo index; and
decode the oligo index based on the most likely path and the plurality of copies of the oligo index.
10 . The system of claim 9 , further comprising:
a reference mark decoder configured to:
receive, based on oligos with a same decoded oligo index, read data determined from sequencing at least two copies of the oligo;
populate a reference mark correlation matrix based on a comparison of reference mark positions in a first copy of the oligo to reference mark positions in a second copy of the oligo;
determine a most likely path through the reference mark correlation matrix corresponding to offset values for the plurality of reference marks;
determine, based on at least one offset value for the plurality of reference marks, an insertion or deletion in a data segment between sequential reference marks; and
correct symbol alignment in the data segment to compensate for the insertion or deletion; and
a user data decoder configured to:
decode the user data from the read data using an error correction code and corresponding redundancy data; and
output, based on the decoded user data, the data unit.
11 . A method comprising:
determining an oligo for encoding a data unit, wherein the oligo encodes a number of symbols corresponding to user data in the data unit;
inserting a plurality of reference marks at a predetermined interval along a length of the oligo, wherein:
at least one set of reference marks in the plurality of reference marks encodes an oligo index; and
the predetermined interval equals a fixed data length between sequential reference marks; and
outputting write data for the oligo for synthesis of the oligo.
12 . The method of claim 11 , wherein the predetermined interval of the plurality of reference marks corresponds to a single base pair between sequential reference marks.
13 . The method of claim 11 , wherein the oligo index comprises:
an oligo address; and
a cyclic redundancy check code.
14 . The method of claim 11 , wherein:
the plurality of reference marks comprises a plurality of copies of the oligo index;
each copy of the oligo index comprises a different set of reference marks of the at least one set of reference marks; and
at least two copies of the oligo index comprise different translations of the oligo index that order the corresponding sets of reference marks in different translation orders.
15 . The method of claim 14 wherein:
each copy of the oligo index:
occupies a predetermined set of positions in the plurality of reference marks; and
has a known translation order for that predetermined set of positions and corresponding set of reference marks; and
the different translation orders are selected from:
mirror symmetry; and
translational symmetry using circular offset values less than a length of the oligo index.
16 . The method of claim 15 , wherein:
the plurality of reference marks comprises a reference number of base pairs in the oligo;
the reference number of base pairs is a multiple of the length of the oligo index;
the multiple is at least equal to a number of the plurality of copies; and
the number of the plurality of copies is at least four.
17 . The method of claim 14 , wherein the different sets of reference marks of the at least two copies are interleaved along the length of the oligo index.
18 . The method of claim 14 , further comprising:
receiving read data determined from sequencing the oligo;
determining, from the read data, a convolutional matrix for the oligo, wherein each column of the convolutional matrix corresponds to a base pair offset of the read data for the oligo;
determining, from the read data, a first reference matrix based on a first sequence of reference positions at an encoded frequency of the plurality of reference marks;
determining, from the read data, a second reference matrix based on a second sequence of reference positions at the encoded frequency of the plurality of reference marks;
determining a first correlation matrix based on a comparison of the convolutional matrix to the first reference matrix;
determining a second correlation matrix based on a comparison of the convolutional matrix and the second reference matrix;
determining a most likely path through a combination of the first correlation matrix and the second correlation matrix based on:
a series of probabilities of moving between corresponding rows in the first correlation matrix and the second correlation matrix; and
loop decoding for different symmetries of the plurality of copies of the oligo index; and
decoding the oligo index based on the most likely path and the plurality of copies of the oligo index.
19 . The method of claim 18 , further comprising:
receiving, based on oligos with a same decoded oligo index, read data determined from sequencing at least two copies of the oligo;
populating a reference mark correlation matrix based on a comparison of reference mark positions in a first copy of the oligo to reference mark positions in a second copy of the oligo;
determining a most likely path through the reference mark correlation matrix corresponding to offset values for the plurality of reference marks;
determining, based on at least one offset value for the plurality of reference marks, an insertion or deletion in a data segment between sequential reference marks;
correcting symbol alignment in the data segment to compensate for the insertion or deletion;
decoding the user data from the read data using an error correction code and corresponding redundancy data; and
outputting, based on the decoded user data, the data unit.
20 . A system comprising:
means for determining an oligo for encoding a data unit, wherein the oligo encodes a number of symbols corresponding to user data in the data unit;
means for inserting a plurality of reference marks at a predetermined interval along a length of the oligo, wherein:
at least one set of reference marks in the plurality of reference marks encodes an oligo index; and
the predetermined interval equals a fixed data length between sequential reference marks; and
means for outputting write data for the oligo for synthesis of the oligo.