2020/10/06 by Jinping Fan, Hung‐Lin Fu, Fan, Jinping +7
Biochemistry, Genetics and Molecular Biology · Medicine · #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #Data-Driven Disease Surveillance #FOS: Mathematics #SARS-CoV-2 detection and testing
paper · pdf · doi:10.48550/arxiv.2010.02518
openalex publication_date 2020/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In nonadaptive combinatorial group testing (CGT), it is desirable to identify a small set of up to d defectives from a large population of n items with as few tests (i.e. large rate) and efficient identifying algorithm as possible. In the literature, d-disjunct matrices (d-DM) and d-separable matrices (d-SM) are two classical combinatorial structures having been studied for several decades. It is well-known that a d-DM provides a more efficient identifying algorithm than a d-SM, while a d-SM could have a larger rate than a d-DM. In order to combine the advantages of these two structures, in this paper, we introduce a new notion of strongly d-separable matrix (d-SSM) for nonadaptive CGT and show that a d-SSM has the same identifying ability as a d-DM, but much weaker requirements than a d-DM. Accordingly, the general bounds on the largest rate of a d-SSM are established. Moreover, by the random coding method with expurgation, we derive an improved lower bound on the largest rate of a 2-SSM which is much higher than the best known result of a 2-DM.