Microsoft Corporation
TRELLIS BASED RECONSTRUCTION ALGORITHMS AND INNER CODES FOR DNA DATA STORAGE

Abstract:

Techniques for achieving reductions in cost of encoding and decoding operations used in DNA data storage systems to facilitate reducing errors in those encoding and decoding operations while accounting for a code structure used during the encoding and decoding by constructing and using insertion-deletion-substitution (IDS) trellises for multiple traces are disclosed. A DNA sequencing channel is used to randomly sample and sequence DNA strands to generate noisy traces. Multiple trellises are independently constructed for each respective noisy trace. A forward-backward algorithm is run on each trellis to compute posterior marginal probabilities for vertices included in each trellises. An estimate of the data message sequence is then computed.