---
res:
bibo_abstract:
- '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.@eng'
bibo_authorlist:
- autoren_ansetzung:
- Cicalese, Ferdinando
- Cicalese
- Ferdinando Cicalese
- Cicalese, F
- Cicalese, F.
- F Cicalese
- F. Cicalese
foaf_Person:
foaf_givenName: Ferdinando
foaf_name: Cicalese, Ferdinando
foaf_surname: Cicalese
luAuthorMark: '1'
- autoren_ansetzung:
- Damaschke, Peter
- Damaschke
- Peter Damaschke
- Damaschke, P
- Damaschke, P.
- P Damaschke
- P. Damaschke
foaf_Person:
foaf_givenName: Peter
foaf_name: Damaschke, Peter
foaf_surname: Damaschke
- autoren_ansetzung:
- Tansini, Libertad
- Tansini
- Libertad Tansini
- Tansini, L
- Tansini, L.
- L Tansini
- L. Tansini
foaf_Person:
foaf_givenName: Libertad
foaf_name: Tansini, Libertad
foaf_surname: Tansini
- autoren_ansetzung:
- Werth, Soeren
- Werth
- Soeren Werth
- Werth, S
- Werth, S.
- S Werth
- S. Werth
foaf_Person:
foaf_givenName: Soeren
foaf_name: Werth, Soeren
foaf_surname: Werth
bibo_doi: 10.1007/11533719_94
dct_date: 2005^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
dct_language: eng
dct_title: 'Overlaps Help: Improved Bounds for Group Testing with Interval Queries@'
...