Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of , the design and analysis of high-rate efficiently encodable codes that can be efficiently decoded with high probability from few reads (also called ) corrupted by edit errors. Codes used in current portable DNA-based storage systems with nanopore sequencers are largely based on heuristics, and have no provable robustness or performance guarantees even for an error model with i.i.d. deletions and constant deletion probability. Our work is a first step towards the design of efficient codes with provable guarantees for such systems. We consider a constant rate of i.i.d. deletions, and perform an analysis of marker-based code-constructions. This gives rise to codes with redundancy @math (resp. @math ) that can be efficiently reconstructed from @math (resp. @math ) traces, where @math is the message length. Then, we give a construction of a code with @math bits of redundancy that can be efficiently reconstructed from @math traces if the deletion probability is small enough. Finally, we show how to combine both approaches, giving rise to an efficient code with @math bits of redundancy which can be reconstructed from @math traces for a small constant deletion probability.
@cite_31: The problem of reconstructing a sequence when observed through multiple looks over deletion channels occurs in “de novo” DNA sequencing. The DNA could be sequenced multiple times, yielding several “looks” of it, but each time the sequencer could be noisy with (independent) deletion impairments. The main goal of this paper is to develop reconstruction algorithms for a sequence observed through the lens of a fixed number of deletion channels. We use the probabilistic model of the deletion channels to develop both symbol-wise and sequence maximum likelihood decoding criteria, and algorithms motivated by them. Numerical evaluations demonstrate improvement in terms of edit distance error, over earlier algorithms,
@cite_49: We consider the question of the capacity of the deletion channel when multiple copies of the codeword are sent independently through the channel. This type of coding problem is straightforward for standard erasure and error channels, but is more challenging in the deletion channel setting. Our results show that when the same codeword is sent k times through the channel, each time with independent deletions with probability d, the optimal communication rate under a random codebook is 1 − αH(dk) + O(dk) for an explicitly given constant α.
Coded trace reconstruction is also related to the multi-use deletion channel. In fact, the decoding problem for this channel can be interpreted as coded trace reconstruction with a fixed number of traces. Some results are known about the capacity of this channel for small deletion probability @cite_49 , and about maximum likelihood decoding @cite_31 .