Coded Trace Reconstruction

Mahdi Cheraghchi, Joao Ribeiro, Ryan Gabrys, Olgica Milenkovic

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of 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 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 begin by analyzing marker-based code-constructions coupled with worst-case trace reconstruction algorithms. Then, we show how a more careful design of the code allows us to exploit ideas from average-case trace reconstruction to reduce the number of traces required with the same redundancy.

Original languageEnglish (US)
Title of host publication2019 IEEE Information Theory Workshop, ITW 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538669006
StatePublished - Aug 2019
Event2019 IEEE Information Theory Workshop, ITW 2019 - Visby, Sweden
Duration: Aug 25 2019Aug 28 2019

Publication series

Name2019 IEEE Information Theory Workshop, ITW 2019


Conference2019 IEEE Information Theory Workshop, ITW 2019

ASJC Scopus subject areas

  • Software
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Information Systems


Dive into the research topics of 'Coded Trace Reconstruction'. Together they form a unique fingerprint.

Cite this