Coded Trace Reconstruction. Cheraghchi, M., Gabrys, R., Milenkovic, O., & Ribeiro, J. IEEE Transactions on Information Theory, 66(10):6084-6103, 2020. Preliminary version in Proceedings of ITW 2019.Link Paper doi abstract bibtex 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 perform an analysis of marker-based code-constructions. This gives rise to codes with redundancy $O(n/łog n)$ (resp. $O(n/łogłog n)$) that can be efficiently reconstructed from $\exp(O(łog^{2/3}n))$ (resp. $\exp(O(łogłog n)^{2/3})$) traces, where $n$ is the message length. Then, we give a construction of a code with $O(łog n)$ bits of redundancy that can be efficiently reconstructed from $\mathrm{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/łog n)$ bits of redundancy which can be reconstructed from $\mathrm{poly}(łog n)$ traces for a small constant deletion probability.
@ARTICLE{ref:CGMR20,
author = {Mahdi Cheraghchi and Ryan Gabrys and Olgica
Milenkovic and Jo\~{a}o Ribeiro},
title = {Coded Trace Reconstruction},
year = 2020,
journal = {IEEE Transactions on Information Theory},
note = {Preliminary version in Proceedings of {ITW 2019}.},
doi = {10.1109/TIT.2020.2996377},
volume={66},
number={10},
pages={6084-6103},
url_Link = {https://ieeexplore.ieee.org/document/9097932},
url_Paper = {https://arxiv.org/abs/1903.09992},
abstract = {Motivated by average-case trace reconstruction and
coding for portable DNA-based storage systems, we
initiate the study of \textit{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 \textit{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 $\mathrm{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 $\mathrm{poly}(\log n)$ traces
for a small constant deletion probability. }
}
Downloads: 0
{"_id":"bySuSQzp66Ab6HjAR","bibbaseid":"cheraghchi-gabrys-milenkovic-ribeiro-codedtracereconstruction-2020","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","H4D7r27RcPALT5DCs","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YqipZGeRZYdKe4qK8","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M.","Gabrys, R.","Milenkovic, O.","Ribeiro, J."],"bibdata":{"bibtype":"article","type":"article","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Ryan"],"propositions":[],"lastnames":["Gabrys"],"suffixes":[]},{"firstnames":["Olgica"],"propositions":[],"lastnames":["Milenkovic"],"suffixes":[]},{"firstnames":["João"],"propositions":[],"lastnames":["Ribeiro"],"suffixes":[]}],"title":"Coded Trace Reconstruction","year":"2020","journal":"IEEE Transactions on Information Theory","note":"Preliminary version in Proceedings of ITW 2019.","doi":"10.1109/TIT.2020.2996377","volume":"66","number":"10","pages":"6084-6103","url_link":"https://ieeexplore.ieee.org/document/9097932","url_paper":"https://arxiv.org/abs/1903.09992","abstract":"Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of <i>coded trace reconstruction</i>, the design and analysis of high-rate efficiently encodable codes that can be efficiently decoded with high probability from few reads (also called <i>traces</i>) 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/łog n)$ (resp. $O(n/łogłog n)$) that can be efficiently reconstructed from $\\exp(O(łog^{2/3}n))$ (resp. $\\exp(O(łogłog n)^{2/3})$) traces, where $n$ is the message length. Then, we give a construction of a code with $O(łog n)$ bits of redundancy that can be efficiently reconstructed from $\\mathrm{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/łog n)$ bits of redundancy which can be reconstructed from $\\mathrm{poly}(łog n)$ traces for a small constant deletion probability. ","bibtex":"@ARTICLE{ref:CGMR20,\n author =\t {Mahdi Cheraghchi and Ryan Gabrys and Olgica\n Milenkovic and Jo\\~{a}o Ribeiro},\n title =\t {Coded Trace Reconstruction},\n year =\t 2020,\n journal =\t {IEEE Transactions on Information Theory},\n note =\t {Preliminary version in Proceedings of {ITW 2019}.},\n doi =\t\t {10.1109/TIT.2020.2996377},\n volume={66},\n number={10},\n pages={6084-6103},\n url_Link =\t {https://ieeexplore.ieee.org/document/9097932},\n url_Paper =\t {https://arxiv.org/abs/1903.09992},\n abstract =\t {Motivated by average-case trace reconstruction and\n coding for portable DNA-based storage systems, we\n initiate the study of \\textit{coded trace\n reconstruction}, the design and analysis of\n high-rate efficiently encodable codes that can be\n efficiently decoded with high probability from few\n reads (also called \\textit{traces}) corrupted by\n edit errors. Codes used in current portable\n DNA-based storage systems with nanopore sequencers\n are largely based on heuristics, and have no\n provable robustness or performance guarantees even\n for an error model with i.i.d. deletions and\n constant deletion probability. Our work is a first\n step towards the design of efficient codes with\n provable guarantees for such systems. We consider a\n constant rate of i.i.d. deletions, and perform an\n analysis of marker-based code-constructions. This\n gives rise to codes with redundancy $O(n/\\log n)$\n (resp. $O(n/\\log\\log n)$) that can be efficiently\n reconstructed from $\\exp(O(\\log^{2/3}n))$\n (resp. $\\exp(O(\\log\\log n)^{2/3})$) traces, where\n $n$ is the message length. Then, we give a\n construction of a code with $O(\\log n)$ bits of\n redundancy that can be efficiently reconstructed\n from $\\mathrm{poly}(n)$ traces if the deletion\n probability is small enough. Finally, we show how to\n combine both approaches, giving rise to an efficient\n code with $O(n/\\log n)$ bits of redundancy which can\n be reconstructed from $\\mathrm{poly}(\\log n)$ traces\n for a small constant deletion probability. }\n}\n\n","author_short":["Cheraghchi, M.","Gabrys, R.","Milenkovic, O.","Ribeiro, J."],"key":"ref:CGMR20","id":"ref:CGMR20","bibbaseid":"cheraghchi-gabrys-milenkovic-ribeiro-codedtracereconstruction-2020","role":"author","urls":{" link":"https://ieeexplore.ieee.org/document/9097932"," paper":"https://arxiv.org/abs/1903.09992"},"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"article","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-28T17:18:38.012Z","downloads":10,"keywords":[],"search_terms":["coded","trace","reconstruction","cheraghchi","gabrys","milenkovic","ribeiro"],"title":"Coded Trace Reconstruction","year":2020,"dataSources":["YZqdBBx6FeYmvQE6D"]}