Granted Patent B2

US 12,373,283 · App. 18/356,104 · Granted Jul 29, 2025

Inventors: David Avraham (Even Yehuda, IL); Ran Zamir (Ramat Gan, IL); Alexander Bazarsky (Holon, IL)

Assignee: Western Digital Technologies, Inc.

G06F11/1004G16B30/00G16B50/30

Abstract

Claims (80)

1. A deoxyribonucleic acid (DNA)-based storage system, comprising:

an error correction system operable to:

identify a DNA codeword, the DNA codeword including an information segment and an error correction segment;

calculate an initial syndrome weight for the information segment based, at least in part, on error correction data included in the error correction segment;

determine whether the initial syndrome weight is greater than a predetermined threshold; and

perform an alignment alteration in the information segment based, at least in part, on determining that the initial syndrome weight is greater than the predetermined threshold, wherein performing the alignment alteration corrects one or more insertion/deletion (indel) errors in the information segment.

2. The DNA-based storage system of claim 1 , wherein performing the alignment alteration comprises:

selecting a skew point within the information segment;

performing an indel operation on the information segment at the skew point to generate a modified information segment;

calculating a modified syndrome weight of the modified information segment based, at least in part, on the error correction data;

comparing the initial syndrome weight with the modified syndrome weight; and

generating a modified codeword by incorporating the indel operation into the information segment based, at least in part, on the comparison between the initial syndrome weight and the modified syndrome weight.

3. The DNA-based storage system of claim 1 , wherein the indel operation is a deletion operation and wherein performing the indel operation further comprises:

deleting, from the information segment, an existing DNA base adjacent to the skew point; and

shifting all DNA bases occurring after the skew point within the information segment by at least one base position.

4. The DNA-based storage system of claim 1 , wherein the error correction system is further operable to:

determine whether there is known shaping data associated with the DNA codeword; and

based, at least in part, on determining that there is known shaping data associated with the DNA codeword:

select a first tuple of DNA bases from the information segment, the first tuple of DNA bases occupying a first region of the information segment;

compare the first tuple of DNA bases to a set of valid tuples, thereby identifying that the first tuple is invalid; and

perform one or more indel operations at one or more skew points within the first region.

5. The DNA-based storage system of claim 4 , wherein the performed one or more indel operations is a first indel operation and wherein the error correction system is further operable to incorporate a second indel operation of the one or more indel operations into the information segment based, at least in part, on determining that the second indel operation results in an improved syndrome weight for the information segment.

6. The DNA-based storage system of claim 1 , wherein the error correction system is further operable to:

scan the information segment for an occurrence of one or more error patterns, each error pattern including an ordered sequence of DNA bases;

identify, within the information segment, a first occurrence of a first error pattern based, at least in part, on the scanning, the first occurrence occupying a first region of the information segment; and

perform one or more indel operations at one or more skew points within the first region.

7. The DNA-based storage system of claim 1 , wherein the error correction system is further operable to:

identify an expected length of the information segment;

determine a current length of the information segment from the codeword;

compute a difference between the expected length and the current length; and

perform a number of insertion operations and a number of deletion operations based, at least in part, on the difference, where the performance of the number of insertion operations and the number of deletion operations results in a modified information segment that has a length equal to the expected length.

8. The DNA-based storage system of claim 1 , wherein the indel operation is an insertion operation and wherein performing the indel operation further comprises:

shifting all DNA bases occurring after the skew point within the information segment by the at least one base position; and

inserting a new DNA base at the skew point.

9. The DNA-based storage system of claim 2 , wherein the error correction system is further operable to:

decode the modified codeword to generate at least a portion of an output file, the portion of the output file including data decoded from the modified information segment; and

transmit contents of the output file to a computing device, the output file representing user data associated with the DNA codeword.

10. A method for performing error correction on a deoxyribonucleic acid (DNA) codeword generated through sequencing a DNA molecule, the method comprising:

identifying a DNA codeword, the DNA codeword including at least an information segment and an associated error correction segment;

calculating an initial syndrome weight for the information segment based, at least in part, on error correction data associated with the error correction segment;

determining whether the initial syndrome weight is greater than a predetermined threshold; and

performing an alignment alteration in the information segment based, at least in part, on determining that the initial syndrome weight is greater than the predetermined threshold, wherein performing the alignment alteration corrects one or more insertion/deletion (indel) errors in the information segment.

11. The method of claim 8 , further comprising:

determining whether there is known shaping data associated with the DNA codeword; and

based, at least in part, on determining that there is known shaping data associated with the DNA codeword:

selecting a first tuple of DNA bases from the information segment, the first tuple of DNA bases occupying a first region of the information segment;

comparing the first tuple of DNA bases to a set of valid tuples, thereby identifying that the first tuple is invalid; and

performing one or more indel operations at one or more skew points within the first region.

12. The method of claim 11 , wherein the performed one or more indel operation is a first indel operation and wherein the method further comprises incorporating a second indel operation of the one or more indel operations into the information segment responsive to the second indel operation resulting in an improved syndrome weight for the information segment.

13. The method of claim 8 , further comprising:

scanning the information segment for an occurrence of one or more error patterns, each error pattern including an ordered sequence of DNA bases;

identifying, within the information segment, a first occurrence of a first error pattern based, at least in part, on the scanning, the first occurrence occupying a first region of the information segment; and

performing one or more indel operations at one or more skew points within the first region.

14. The method of claim 8 , further comprising:

identifying an expected length of the information segment;

determining a current length of the information segment from the codeword;

computing a difference between the expected length and the current length; and

performing a number of insertion operations and a number of deletion operations based, at least in part, on the difference, where the performance results in a modified information segment that has a length equal to the expected length.

15. The method of claim 10 , wherein performing the alignment alteration comprises:

selecting a skew point within the information segment;

performing an indel operation on the information segment at the skew point to generate a modified information segment;

calculating a modified syndrome weight of the modified information segment based, at least in part, on the error correction data;

comparing the initial syndrome weight with the modified syndrome weight; and

generating a modified codeword by incorporating the indel operation into the information segment based, at least in part, on the comparison between the initial syndrome weight and the modified syndrome weight.

16. The method of claim 15 , wherein the indel operation is an insertion operation and wherein performing the indel operation further comprises:

shifting all DNA bases occurring after the skew point within the information segment by at least one base position; and

inserting a new DNA base at the skew point.

17. The method of claim 15 , wherein the indel operation is a deletion operation and wherein performing the indel operation further comprises:

deleting, from the information segment, an existing DNA base adjacent to the skew point; and

shifting all of the DNA bases occurring after the skew point within the information segment by at least one base position.

18. The method of claim 15 , wherein the indel operation is incorporated into the information segment based, at least in part, on the comparing the initial syndrome weight with the modified syndrome weight indicating an improvement in the modified syndrome weight when compared to the initial syndrome weight.

19. A control system for a deoxyribonucleic acid (DNA)-based storage system, the control system

means for identifying a DNA codeword from an output string produced from a DNA sequencing operation on a DNA molecule, the DNA codeword including an information segment and an associated error correction segment;

means for calculating an initial syndrome weight for the information segment based, at least in part, on error correction data included in the error correction segment;

means for determining whether the initial syndrome weight is greater than a predetermined threshold; and

means for performing, based at least in part on the determining, an alignment alteration in the information segment.

20. The control system of claim 15 , wherein the control system further comprises:

means for scanning the information segment for an occurrence of one or more error patterns, each error pattern including an ordered sequence of DNA bases;

means for identifying, within the information segment, a first occurrence of a first error pattern based, at least in part, on the scanning, the first occurrence occupying a first region of the information segment; and

means for performing one or more insertion/deletion (indel) operations at one or more skew points within the first region.

Assignments (4)

Continuity (2)

References Cited (18)