Unique Reconstruction of Coded Strings From Multiset Substring Spectra

DOI10.1109/TIT.2019.2935973MaRDI QIDQ5211529zbMATH OpenOpenAlexFDO

Authors Ryan Gabrys, Olgica Milenkovic

Publication date 28 January 2020

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

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

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Abstract: The problem of reconstructing strings from their substring spectra has a long history and in its most simple incarnation asks for determining under which conditions the spectrum uniquely determines the string. We study the problem of coded string reconstruction from multiset substring spectra, where the strings are restricted to lie in some codebook. In particular, we consider binary codebooks that allow for unique string reconstruction and propose a new method, termed repeat replacement, to create the codebook. Our contributions include algorithmic solutions for repeat replacement and constructive redundancy bounds for the underlying coding schemes. We also consider extensions of the problem to noisy settings in which substrings are compromised by burst and random errors. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers.

Cited in

(5)

• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• Spectral concepts in genome informational analysis
• On the number of distinct \(k\)-decks: enumeration and bounds
• A word reconstruction problem for polynomial regular languages
• Improvements on permutation reconstruction from minors

This page was built for publication: Unique Reconstruction of Coded Strings From Multiset Substring Spectra

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