Coded Trace Reconstruction

DOI10.1109/TIT.2020.2996377MaRDI QIDQ5138794zbMATH OpenOpenAlexFDO

Authors Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, João L. Ribeiro

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.09992

zbMATH Keywords

analysisdesignhigh-rate efficiently encodable codesportable DNA-based storage systems

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: 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/logn)$ (resp. $O(n/loglogn)$) that can be efficiently reconstructed from $exp(O(lo{g}^{2/3}n))$ (resp. $exp(O(loglogn{)}^{2/3})$) traces, where $n$ is the message length. Then, we give a construction of a code with $O(logn)$ bits of redundancy that can be efficiently reconstructed from $extrmpoly(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/logn)$ bits of redundancy which can be reconstructed from $extrmpoly(logn)$ traces for a small constant deletion probability.

Cited in

(11)

• Hidden words statistics for large patterns
• New lower bounds for trace reconstruction
• Reconstructing trees from traces
• The trace reconstruction problem for spider graphs
• Binomial complexities and Parikh-collinear morphisms
• Information-Theoretic Foundations of DNA Data Storage
• Tree trace reconstruction using subtraces
• Trace reconstruction from local statistical queries
• Levenshtein's sequence reconstruction problem and results for larger alphabet sizes
• Circular trace reconstruction
• Near-optimal trace reconstruction for mildly separated strings

This page was built for publication: Coded Trace Reconstruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138794)