Group Testing with Runlength Constraints for Topological Molecular Storage

Abhishek Agarwal, Olgica Milenkovic, Srilakshmi Pattabiraman, Joao Ribeiro

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

Abstract

Motivated by applications in topological DNA-based data storage, we introduce and study a novel setting of Non-Adaptive Group Testing (NAGT) with runlength constraints on the columns of the test matrix, in the sense that any two 1's must be separated by a run of at least d 0's. We describe and analyze a probabilistic construction of a runlength-constrained scheme in the zero-error and vanishing error settings, and show that the number of tests required by this construction is optimal up to logarithmic factors in the runlength constraint d and the number of defectives k in both cases. Our results reveal that runlength-constrained NAGT is not more restrictive than unconstrained NAGT when d = O(k), and that for almost all choices of d and k it is not more restrictive than NAGT with a column Hamming weight constraint only.

Original languageEnglish (US)
Title of host publication2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages132-137
Number of pages6
ISBN (Electronic)9781728164328
DOIs
StatePublished - Jun 2020
Event2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States
Duration: Jul 21 2020Jul 26 2020

Publication series

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

Conference

Conference2020 IEEE International Symposium on Information Theory, ISIT 2020
CountryUnited States
CityLos Angeles
Period7/21/207/26/20

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Group Testing with Runlength Constraints for Topological Molecular Storage'. Together they form a unique fingerprint.

Cite this