Coded trace reconstruction

Patent metadata

Field	Value
Publication number	US-12380337-B2
Application number	US-202017069247-A
Country	US
Kind code	B2
Filing date	Oct 13, 2020
Priority date	Oct 24, 2019
Publication date	Aug 5, 2025
Grant date	Aug 5, 2025

Abstract

The present disclosure provides systems and methods that relate to storing encoded information in, and reading the encoded information from, nucleotide sequences. An example method includes receiving, at a DNA readout system, a nucleotide sequence. The method also includes reading the nucleotide sequence based on an alphabet consisting of {adenine (A), cytosine (C), guanine (G), and thymine (T)}. The method further includes determining positions of unique markers between a plurality of encoded blocks in the nucleotide sequence. The method yet further includes decoding each encoded block of the plurality of encoded blocks according to an inner code, so as to form a plurality of decoded blocks. The method also includes appending the decoded blocks to one another to provide a decoded message with message length n bits.

First claim

What is claimed is:

1. A method, comprising:
partitioning a message having a message length n bits into a plurality of blocks with a maximum block length of O(log 2 n);
encoding each block to provide a plurality of encoded blocks;
inserting unique markers between the encoded blocks so as to form an encoded message, wherein the markers each have a minimum marker length O(log n); and
synthesizing a DNA having a nucleotide sequence based on the encoded message.

2. The method of claim 1 , wherein encoding each block comprises encoding according to an inner code, wherein the inner code comprises an alphabet consisting of adenine (A), cytosine (C), guanine (G), and thymine (T).

3. The method of claim 2 , wherein each unique marker is of the form M=(AC) l ∥(TG) l , where l=25 log n.

4. The method of claim 2 , wherein the encoded blocks consist of 50% guanine and cytosine content.

5. The method of claim 1 , wherein encoding each block comprises encoding each block according to a Hamming encoding with a relative Hamming distance.

6. The method of claim 1 , further comprising:
further partitioning each block into a plurality of subblocks; and
inserting a second level of markers between each subblock, wherein the second level of markers is different than the unique markers.

7. A DNA-based data storage system comprising:
a DNA synthesizer; and
a controller configured to carry out operations, the operations including:
partitioning a message having a message length n bits into a plurality of blocks with a maximum block length of O(log 2 n);
encoding each block to provide a plurality of encoded blocks;
inserting unique markers between the encoded blocks so as to form an encoded message, wherein the markers each have a minimum marker length O(log n); and
informing the DNA synthesizer to synthesize a nucleotide sequence based on the encoded message.

8. The DNA-based data storage system of claim 7 , wherein encoding each block comprises encoding according to an inner code, wherein the inner code comprises an alphabet consisting of adenine (A), cytosine (C), guanine (G), and thymine (T).

9. The DNA-based data storage system of claim 8 , wherein each unique marker is of the form M=(AC) l ∥(TG) l , where l=25 log n.

10. The DNA-based data storage system of claim 8 , wherein the encoded blocks consist of 50% guanine and cytosine content.

11. The DNA-based data storage system of claim 7 , wherein encoding each block comprises encoding each block according to a Hamming encoding with a relative Hamming distance.

12. The DNA-based data storage system of claim 7 , wherein the operations further comprise:
further partitioning each block into a plurality of subblocks; and
inserting a second level of markers between each subblock, wherein the second level of markers is different than the unique markers.

Assignees

• Univ Illinois
• Imperial College Innovations Ltd

Inventors

• Milenkovic Olgica
• Gabrys Ryan
• Ribeiro João
• Astaneh Mahdi Cheraghchi Bashi

Classifications

• G06N3/126

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• C12N15/1065 Primary

  Preparation or screening of tagged libraries, e.g. tagged microorganisms by STM-mutagenesis, tagged polynucleotides, gene tags · CPC title

• C12Q1/6869

  Methods for sequencing · CPC title

• G06N3/123 Primary

  DNA computing · CPC title