TY - GEN
T1 - Unique Reconstruction of Coded Sequences from Multiset Substring Spectra
AU - Gabrys, Ryan
AU - Milenkovic, Olgica
N1 - Funding Information:
Acknowledgment. The work was supported by the NSF grant CCF 1618366.
Funding Information:
The work was supported by the NSF grant CCF 1618366.
Publisher Copyright:
© 2018 IEEE.
PY - 2018/8/15
Y1 - 2018/8/15
N2 - 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. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers.
AB - 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. The study is motivated by applications in DNA-based data storage systems that use high throughput readout sequencers.
UR - http://www.scopus.com/inward/record.url?scp=85052439520&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052439520&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2018.8437909
DO - 10.1109/ISIT.2018.8437909
M3 - Conference contribution
AN - SCOPUS:85052439520
SN - 9781538647806
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2540
EP - 2544
BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018
Y2 - 17 June 2018 through 22 June 2018
ER -