Flexible decoding in DNA data storage based on redundancy codes

1. A method comprising:

in a first pass through a plurality of nucleotide symbol strings representing nucleotide strand sequence reads from a polynucleotide sequencer, wherein the nucleotide strand sequence reads represent logically ordered nucleotide symbol strings comprising encoded data with redundancy information, placing a nucleotide symbol string representing a solitary nucleotide strand sequence read in a first order position of an ordered map; and

in a second pass through the nucleotide symbol strings representing nucleotide strand sequence reads from the polynucleotide sequencer, performing cluster-based trace reconstruction, wherein the cluster-based trace reconstruction generates a reconstructed nucleotide symbol string and places the reconstructed nucleotide symbol string in a second order position of the ordered map;

wherein the ordered map maps nucleotide symbol strings to positions in an overall ordering of data to be decoded.

2. The method of claim 1 wherein:

the first pass comprises performing integrity verification on the nucleotide symbol string representing the solitary nucleotide strand sequence read; and

placing in the first order position is performed responsive to determining that the nucleotide symbol string representing the solitary nucleotide strand sequence read passes integrity verification.

3. The method of claim 2 wherein:

the integrity verification of the nucleotide symbol string comprises performing integrity verification with redundancy nucleotide symbols originating from the solitary nucleotide strand sequence read.

4. The method of claim 2 wherein the method further comprises:

during the first pass, before integrity verification, performing error correction on the nucleotide symbol string with redundancy nucleotide symbols originating from the solitary nucleotide strand sequence read.

5. The method of claim 2 wherein:

redundancy nucleotide symbols in the solitary nucleotide strand sequence read are partitioned into a first part and second part; and

the first pass comprises implementing error correction for the solitary nucleotide strand sequence read with the first part and implementing integrity verification for the solitary nucleotide strand sequence read with the second part.

6. The method of claim 5 wherein:

the error correction corrects a substitution error.

7. The method of claim 5 wherein:

the error correction corrects an insertion or deletion error.

8. The method of claim 1 further comprising:

forming a cluster of a subset of the nucleotide symbol strings;

wherein the cluster-based trace reconstruction generates the reconstructed nucleotide symbol string based on the cluster.

9. The method of claim 1 further comprising:

responsive to determining, during the first pass, that a plurality of different, conflicting nucleotide symbol strings appear to be mapped to a single position, postponing processing for the conflicting nucleotide symbol strings until the second pass.

10. The method of claim 1 further comprising:

outputting an ordered list of nucleotide symbol strings representing the encoded data;

wherein the ordered list comprises the nucleotide symbol string representing a solitary nucleotide strand sequence read based on the nucleotide strand sequence read in the first order position; and

wherein the ordered list comprises the reconstructed nucleotide symbol string in the second order position.

11. The method of claim 1 wherein:

the second pass incorporates the solitary nucleotide strand sequence read in the cluster-based trace reconstruction.

12. The method of claim 1 further comprising:

removing a cluster in which the solitary nucleotide strand sequence read appears from the cluster-based trace reconstruction.

13. A system comprising:

one or more processors;

memory coupled to the one or more processors;

a string position map storing a mapping between addresses and nucleotide symbol strings;

wherein the memory comprises computer-executable instructions causing the one or more processors to perform operations comprising:

during processing of a nucleotide symbol string representing a solitary strand read by a sequencer, responsive to determining that the nucleotide symbol string representing the solitary strand read by the sequencer passes integrity verification, placing the nucleotide symbol string into the string position map; and

during processing of a cluster of nucleotide symbol strings representing a plurality of strands read by the sequencer, reconstructing a reconstructed nucleotide symbol string based on the cluster and placing the reconstructed nucleotide symbol string into the string position map.

14. The system of claim 13 wherein:

the solitary strand and the plurality of strands read by the sequencer represent logically ordered nucleotide symbol strings comprising encoded data with redundancy information that represents an original data file.

15. The system of claim 13 wherein:

the nucleotide symbol string representing the solitary strand read by the sequencer comprises redundancy information configured to correct one or more substitution errors; and

the operations further comprise:

correcting the nucleotide symbol string before placing it into the string position map.

16. The system of claim 13 wherein:

the nucleotide symbol string representing the solitary strand read by the sequencer comprises redundancy information configured to correct one or more insertion or deletion errors; and

the operations further comprise:

correcting the nucleotide symbol string before placing it into the string position map.

17. The system of claim 13 wherein:

the nucleotide symbol string representing the solitary strand read by the sequencer comprises inner redundancy information partitioned into two portions, wherein one portion is configured to correct one or more substitution errors and another portion is configured to correct one or more insertion or deletion errors; and

the operations further comprise:

correcting the nucleotide symbol string with one of the portions before placing it into the string position map; and

verifying integrity of the nucleotide symbol string with another of the portions before placing it into the string position map.

18. The system of claim 13 wherein the operations further comprise:

removing a cluster in which the nucleotide symbol string representing the solitary strand appears from consideration during cluster-based trace reconstruction.

19. The system of claim 13 wherein the operations further comprise:

incorporating the nucleotide symbol string representing the solitary strand in a cluster formation process during cluster-based trace reconstruction.

20. One or more computer-readable media not consisting of a signal comprising:

computer-executable instructions capable of causing a computing system to place, in a first order position of an ordered map, a nucleotide symbol string representing a solitary nucleotide strand sequence read, wherein the nucleotide symbol string is one out of a plurality of nucleotide symbol strings representing respective nucleotide strand sequence reads from a polynucleotide sequencer, wherein the nucleotide strand sequence reads represent logically ordered comprising encoded data with redundancy information, and wherein the nucleotide symbol string is placed in the first order position of the ordered map responsive to determining that the nucleotide symbol string representing the solitary nucleotide strand sequence read passes integrity verification; and

computer-executable instructions capable of causing the computing system to perform cluster-based trace reconstruction on the plurality of nucleotide symbol strings, wherein the cluster-based trace reconstruction generates a reconstructed nucleotide symbol string out of a cluster of the plurality of nucleotide symbol strings and places the reconstructed nucleotide symbol string in a second order position of the ordered map.