Threshold group testing with consecutive positives

Threshold group testing introduced by Damaschke (2006) is a generalization of classical group testing where a group test yields a positive (negative) outcome if it contains at least u (at most l) positive items, and an arbitrary outcome for otherwise. Motivated by applications to DNA sequencing, gro...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2014-05, Vol.169, p.68-72
Main Authors: Chang, Huilan, Tsai, Yi-Lin
Format: Article
Language:English
Subjects:
Adaptive algorithms
Consecutive positives
Gene sequencing
Group testing
Lower bounds
Mathematical analysis
Sequential algorithm
Subroutines
Threshold
Thresholds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Threshold group testing introduced by Damaschke (2006) is a generalization of classical group testing where a group test yields a positive (negative) outcome if it contains at least u (at most l) positive items, and an arbitrary outcome for otherwise. Motivated by applications to DNA sequencing, group testing with consecutive positives has been proposed by Balding and Torney (1997) and Colbourn (1999) where n items are linearly ordered and up to d positive items are consecutive in the order. In this paper, we introduce threshold-constrained group tests to group testing with consecutive positives. We prove that all positive items can be identified in ⌈log2(⌈n/u⌉−1)⌉+2⌈log2(u+2)⌉+⌈log2(d−u+1)⌉−2 tests for the gap-free case (u=l+1) while the information-theoretic lower bound is ⌈log2n(d−u+1)⌉−1 when n≥d+u−2 and for u=1 the best adaptive algorithm provided by Juan and Chang (2008) takes at most ⌈log2n⌉+⌈log2d⌉ tests. We further show that the case with a gap (u>l+1) can be dealt with by the subroutines used to conquer the gap-free case.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2013.12.013