Error Bounds for Decoding Piecewise Constant Nanopore Signals in DNA Storage
Adrian Vidal, V. B. Wijekoon, Emanuele Viterbo · 2023
Nanopore sequencing enables reading strings of A,C,G,T nucleotides in DNA strands by pulling them into nanopores with the help of motor proteins. Due to the discrete stepping of motor proteins, the signals produced by a DNA sequence tend to be piecewise-constant expansions of some underlying real-valued sequence. In this paper, we assume that every k-nucleotide sequence corresponds to a real-valued codeword of length$k$, and model the nanopore channel as a noisy duplication channel that stretches every sample of a codeword using a geometric distribution, and then adds Gaussian noise. We show that for this channel, a simpler variant of the dynamic time warping (DTW) algorithm performs maximum likelihood decoding. Next, we devise an$O(k^{2})$- algorithm for bounding the pairwise error probability between two codewords of length$k$. Finally, we use Scrappie to design codebooks with a storage efficiency of 1 bit per nucleotide and demonstrate using error simulations the accuracy of the calculated error bounds.