TY - GEN

T1 - The hybrid k-deck problem

T2 - 2017 IEEE International Symposium on Information Theory, ISIT 2017

AU - Gabrys, Ryan

AU - Milenkovic, Olgica

N1 - Funding Information:
Acknowledgement. This research was supported in part by the NSF grants CIF CCS 1526875 and 1618366, and the NSF STC Center for Science of Information at Purdue University.

PY - 2017/8/9

Y1 - 2017/8/9

N2 - We introduce a new variant of the k-deck problem, which in its traditional formulation asks for determining the smallest k that allows one to reconstruct any binary sequence of length n from the multiset of its k-length subsequences. In our version of the problem, termed the hybrid k-deck problem, one is given a certain number of special subsequences of the sequence of length n - t, t > 0, and the question of interest is to determine the smallest value of k such that the k-deck, along with the subsequences, allows for reconstructing the original sequence in an error-free manner. We first consider the case that one is given a single subsequence of the sequence of length n - t, obtained by deleting zeros only, and seek the value of k that allows for hybrid reconstruction. We prove that in this case, k [log t + 2, min{t + 1, O(√n)}]. We then proceed to extend the single-subsequence setup to the case where one is given M subsequences of length n - t obtained by deleting zeroes only. In this case, we first aggregate the asymmetric traces and then invoke the single-trace results. The analysis and problem at hand are motivated by nanopore sequencing problems for DNA-based data storage.

AB - We introduce a new variant of the k-deck problem, which in its traditional formulation asks for determining the smallest k that allows one to reconstruct any binary sequence of length n from the multiset of its k-length subsequences. In our version of the problem, termed the hybrid k-deck problem, one is given a certain number of special subsequences of the sequence of length n - t, t > 0, and the question of interest is to determine the smallest value of k such that the k-deck, along with the subsequences, allows for reconstructing the original sequence in an error-free manner. We first consider the case that one is given a single subsequence of the sequence of length n - t, obtained by deleting zeros only, and seek the value of k that allows for hybrid reconstruction. We prove that in this case, k [log t + 2, min{t + 1, O(√n)}]. We then proceed to extend the single-subsequence setup to the case where one is given M subsequences of length n - t obtained by deleting zeroes only. In this case, we first aggregate the asymmetric traces and then invoke the single-trace results. The analysis and problem at hand are motivated by nanopore sequencing problems for DNA-based data storage.

UR - http://www.scopus.com/inward/record.url?scp=85034066030&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85034066030&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2017.8006740

DO - 10.1109/ISIT.2017.8006740

M3 - Conference contribution

AN - SCOPUS:85034066030

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1306

EP - 1310

BT - 2017 IEEE International Symposium on Information Theory, ISIT 2017

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 25 June 2017 through 30 June 2017

ER -