TY - GEN
T1 - Group Testing with Runlength Constraints for Topological Molecular Storage
AU - Agarwal, Abhishek
AU - Milenkovic, Olgica
AU - Pattabiraman, Srilakshmi
AU - Ribeiro, Joao
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/6
Y1 - 2020/6
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85090413411&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85090413411&partnerID=8YFLogxK
U2 - 10.1109/ISIT44484.2020.9174502
DO - 10.1109/ISIT44484.2020.9174502
M3 - Conference contribution
AN - SCOPUS:85090413411
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 132
EP - 137
BT - 2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2020 IEEE International Symposium on Information Theory, ISIT 2020
Y2 - 21 July 2020 through 26 July 2020
ER -