×

Probabilistic nonadaptive and two-stage group testing with relatively small pools and DNA library screening. (English) Zbl 1002.92551

Summary: We use a simple, but nonstandard, incidence relation to construct probabilistic nonadaptive group testing algorithms that identify many positives in a population with a zero probability of yielding a false positive. More importantly, we give two-stage modifications of our nonadaptive algorithms that dramatically reduce the expected number of sufficient pools. For our algorithms, we give a lower bound on the probability of identifying all the positives and we compute the expected number of positives identified. Our method gives control over the pool size. In DNA library screening algorithms, where relatively small pools are generally preferred, having control over the pool sizes is an important practical consideration.

MSC:

92D20 Protein sequences, DNA sequences
Full Text: DOI