Trellis based reconstruction algorithms and inner codes for dna data storage

A method configured to facilitate reductions in cost of encoding and decoding operations used in deoxyribonucleic acid (DNA) data storage systems and to facilitate reducing errors in said encoding and decoding operations while accounting for a code structure used during said encoding and decoding by constructing and using insertion-deletion-substitution (IDS) trellises for multiple traces, said method comprising:

• after a data message sequence, which includes a plurality of symbols, has been encoded into a DNA sequence and after the DNA sequence has been synthesized into a plurality of DNA strands, using a DNA sequencing channel to randomly sample and sequence K DNA strands included among the plurality of DNA strands, wherein:
• said sequencing results in a generation of K noisy traces of the DNA sequence, wherein K is a number greater than 1, and
• the DNA sequencing channel is modeled as a simplistic zeroth order approximation in a form of an IDS channel;
• independently constructing a corresponding trellis for each respective noisy trace in the K noisy traces such that K trellises are independently constructed, wherein the IDS channel is modeled as a finite state machine (FSM) to construct each of the K trellises;
• running a forward-backward algorithm on each of the K trellises to compute posterior marginal probabilities for vertices included in each of the K trellises;
• computing an estimate of the data message sequence by iterating through the following steps until all estimated symbols forming the estimate of the data message sequence are determined:
• for a given symbol that is to be included in the estimate of the data message sequence, computing a current probability-based belief that each of the K trellises has regarding what the given symbol should be such that a plurality of current probability-based beliefs are computed, said current probability-based beliefs being computed based on the posterior marginal probabilities included in each of the K trellises;
• selecting a particular symbol as the given symbol based on an aggregation of the plurality of current probability-based beliefs;
• identifying certain vertices in each of the K trellises, said certain vertices being identified as a result of the certain vertices disagreeing, based on those certain vertices' corresponding posterior marginal probabilities, with the decision to select the particular symbol as the given symbol;
• updating those certain vertices by updating the posterior marginal probabilities for those certain vertices based on the decision;
• performing forward passes on the K trellises to update the K trellises based on updating the certain vertices;
• and
• adding the particular symbol to the estimate of the data message sequence.

One or more hardware storage devices that store instructions that are executable by one or more processors of a computer system to cause the computer system to at least:

• after a data message sequence, which includes a plurality of symbols, has been encoded into a DNA sequence and after the DNA sequence has been synthesized into a plurality of DNA strands, use a DNA sequencing channel to randomly sample and sequence K DNA strands included among the plurality of DNA strands, wherein:
• said sequencing results in a generation of K noisy traces of the DNA sequence, wherein K is a number greater than 1, and
• the DNA sequencing channel is modeled as a simplistic zeroth order approximation in a form of an IDS channel;
• independently construct a corresponding trellis for each respective noisy trace in the K noisy traces such that K trellises are independently constructed, wherein the IDS channel is modeled as a finite state machine (FSM) to construct each of the K trellises;
• run a forward-backward algorithm on each of the K trellises to compute posterior marginal probabilities for vertices included in each of the K trellises;
• compute an estimate of the data message sequence by iterating through the following steps until all estimated symbols forming the estimate of the data message sequence are determined:
• for a given symbol that is to be included in the estimate of the data message sequence, compute a current probability-based belief that each of the K trellises has regarding what the given symbol should be such that a plurality of current probability-based beliefs are computed, said current probability-based beliefs being computed based on the posterior marginal probabilities included in each of the K trellises;
• select a particular symbol as the given symbol based on an aggregation of the plurality of current probability-based beliefs;
• identify certain vertices in each of the K trellises, said certain vertices being identified as a result of the certain vertices disagreeing, based on those certain vertices' corresponding posterior marginal probabilities, with the decision to select the particular symbol as the given symbol;
• update those certain vertices by updating the posterior marginal probabilities for those certain vertices based on the decision;
• perform forward passes on the K trellises to update the K trellises based on updating the certain vertices;
• and
• add the particular symbol to the estimate of the data message sequence.