  Motivated by average-case trace reconstruction and coding for portable
DNA-based storage systems, we initiate the study of \emph{coded trace
reconstruction}, the design and analysis of high-rate efficiently encodable
codes that can be efficiently decoded with high probability from few reads
(also called \emph{traces}) 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 $O(n/\log n)$ (resp.\ $O(n/\log\log n)$) that can be
efficiently reconstructed from $\exp(O(\log^{2/3}n))$ (resp.\ $\exp(O(\log\log
n)^{2/3})$) traces, where $n$ is the message length. Then, we give a
construction of a code with $O(\log n)$ bits of redundancy that can be
efficiently reconstructed from $\textrm{poly}(n)$ traces if the deletion
probability is small enough. Finally, we show how to combine both approaches,
giving rise to an efficient code with $O(n/\log n)$ bits of redundancy which
can be reconstructed from $\textrm{poly}(\log n)$ traces for a small constant
deletion probability.
