The hybrid k-deck problem: Reconstructing sequences from short and long traces

Ryan Gabrys, Olgica Milenkovic

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

Abstract

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.

Original languageEnglish (US)
Title of host publication2017 IEEE International Symposium on Information Theory, ISIT 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1306-1310
Number of pages5
ISBN (Electronic)9781509040964
DOIs
StatePublished - Aug 9 2017
Event2017 IEEE International Symposium on Information Theory, ISIT 2017 - Aachen, Germany
Duration: Jun 25 2017Jun 30 2017

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095

Other

Other2017 IEEE International Symposium on Information Theory, ISIT 2017
CountryGermany
CityAachen
Period6/25/176/30/17

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'The hybrid k-deck problem: Reconstructing sequences from short and long traces'. Together they form a unique fingerprint.

  • Cite this

    Gabrys, R., & Milenkovic, O. (2017). The hybrid k-deck problem: Reconstructing sequences from short and long traces. In 2017 IEEE International Symposium on Information Theory, ISIT 2017 (pp. 1306-1310). [8006740] (IEEE International Symposium on Information Theory - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT.2017.8006740