---
res:
bibo_abstract:
- 'The classical Group Testing Problem is: Given a finite set of items {1, 2,...,
n} and an unknown subset P subset of {1, 2,..., n} of up to p positive elements,
identify P by asking the least number of queries of the type "does the subset
Q subset of {1,2,...,n} intersect P?". In our case, Q must be a subset of consecutive
elements. This problem naturally arises in several scenarios, most notably in
Computational Biology. We focus on algorithms in which queries are arranged in
stages: in each stage, queries can be performed in parallel, and be chosen depending
on the answers to queries in previous stages. Algorithms that operate in few stages
are usually preferred in practice. First we study the case p = 1 comprehensively.
For two-stage strategies for arbitrary p we obtain asymptotically tight bounds
on the number of queries. Furthermore we prove bounds for any number of stages
and positives, and we discuss the problem with the restriction that query intervals
have some bounded length d.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Ferdinando
foaf_name: Cicalese, Ferdinando
foaf_surname: Cicalese
- foaf_Person:
foaf_givenName: Peter
foaf_name: Damaschke, Peter
foaf_surname: Damaschke
- foaf_Person:
foaf_givenName: Ugo
foaf_name: Vaccaro, Ugo
foaf_surname: Vaccaro
bibo_doi: 10.1007/11428848_130
bibo_volume: 3515
dct_date: 2005^xs_gYear
dct_identifier:
- UT:000230023800130
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
dct_language: eng
dct_publisher: Springer@
dct_title: Optimal group testing strategies with interval queries and their application
to splice site detection@
...