10.1007/11533719_94
Cicalese, Ferdinando
Ferdinando
Cicalese
Damaschke, Peter
Peter
Damaschke
Tansini, Libertad
Libertad
Tansini
Werth, Soeren
Soeren
Werth
Overlaps Help: Improved Bounds for Group Testing with Interval Queries
2005
2011-08-05T09:03:18Z
2018-07-24T12:59:56Z
conference
https://pub.uni-bielefeld.de/record/2308867
https://pub.uni-bielefeld.de/record/2308867.json
0302-9743
Given a finite ordered set of items and an unknown distinguished subset P of up to p positive elements, identify the items in P by asking the least number of queries of the type "does the subset Q intersect P?", where Q is a subset of consecutive elements of {1, 2,..., n}. This problem arises e.g. in computational biology, in a particular method for determining splice sites. We consider time-efficient algorithms where queries are arranged in a fixed number s of stages: in each stage, queries are performed in parallel. In a recent paper we devised query-optimal strategies in the special cases p = 1 or s = 2, subject to lower-order terms. Exploiting new ideas we are now able to provide a much neater argument that allows doubling the general lower bound for any p ! 2 and s >= 3. Moreover, we provide new strategies that match this new bound up to the constant of the main term. The new query scheme shows an effective use of overlapping queries within a stage. Remarkably, this contrasts with the known results for s <= 2 where optimal strategies were implemented by disjoint queries.