Overlaps Help: Improved Bounds for Group Testing with Interval Queries

Cicalese F, Damaschke P, Tansini L, Werth S (2005)
In: Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Lecture Notes in Computer Science, 3595, . 935-944.

Conference Paper | Published | English

No fulltext has been uploaded

Author
; ; ;
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.
Publishing Year
Conference
11th Annual International Conference on Computing and Combinatorics (COCOON 2005)
ISSN
PUB-ID

Cite this

Cicalese F, Damaschke P, Tansini L, Werth S. Overlaps Help: Improved Bounds for Group Testing with Interval Queries. In: Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Lecture Notes in Computer Science, 3595. 2005: 935-944.
Cicalese, F., Damaschke, P., Tansini, L., & Werth, S. (2005). Overlaps Help: Improved Bounds for Group Testing with Interval Queries. Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005), 935-944.
Cicalese, F., Damaschke, P., Tansini, L., and Werth, S. (2005). “Overlaps Help: Improved Bounds for Group Testing with Interval Queries” in Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005) Lecture Notes in Computer Science, 3595 935-944.
Cicalese, F., et al., 2005. Overlaps Help: Improved Bounds for Group Testing with Interval Queries. In Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Lecture Notes in Computer Science, 3595. pp. 935-944.
F. Cicalese, et al., “Overlaps Help: Improved Bounds for Group Testing with Interval Queries”, Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005), Lecture Notes in Computer Science, 3595, 2005, pp.935-944.
Cicalese, F., Damaschke, P., Tansini, L., Werth, S.: Overlaps Help: Improved Bounds for Group Testing with Interval Queries. Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Lecture Notes in Computer Science, 3595. p. 935-944. (2005).
Cicalese, Ferdinando, Damaschke, Peter, Tansini, Libertad, and Werth, Soeren. “Overlaps Help: Improved Bounds for Group Testing with Interval Queries”. Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). 2005. Lecture Notes in Computer Science, 3595. 935-944.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Search this title in

Google Scholar