Overlaps help: Improved bounds for group testing with interval queries

Cicalese F, Damaschke P, Tansini L, Werth S (2007)
Discrete Applied Mathematics 155(3): 288-299.

Journal Article | 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 1) 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 in genes. 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 bioinformatics paper, we proved optimality (subject to lower-order terms) with respect to the number of queries, of some strategies for the special cases p = 1 or s = 2. Exploiting new ideas, we are now able to provide improved lower bounds for any p >= 2 and s >= 3 and improved upper bounds for larger s. Most notably, our new bounds converge as s grows. Our new query scheme uses overlapping query intervals within a stage, which is effective for large enough s. This contrasts with our previous results for s <= 2 where optimal strategies were implemented by disjoint queries. The main open problem is whether overlaps help already in the case of small s >= 3. Anyway, the remaining gaps between the current upper and lower bounds for any fixed s >= 3 amount to small constant factors in the main term. The paper ends with a discussion of practical implications in the case that the positive elements are well separated. (c) 2006 Elsevier B.V. All rights reserved.
Publishing Year
ISSN
PUB-ID

Cite this

Cicalese F, Damaschke P, Tansini L, Werth S. Overlaps help: Improved bounds for group testing with interval queries. Discrete Applied Mathematics. 2007;155(3):288-299.
Cicalese, F., Damaschke, P., Tansini, L., & Werth, S. (2007). Overlaps help: Improved bounds for group testing with interval queries. Discrete Applied Mathematics, 155(3), 288-299.
Cicalese, F., Damaschke, P., Tansini, L., and Werth, S. (2007). Overlaps help: Improved bounds for group testing with interval queries. Discrete Applied Mathematics 155, 288-299.
Cicalese, F., et al., 2007. Overlaps help: Improved bounds for group testing with interval queries. Discrete Applied Mathematics, 155(3), p 288-299.
F. Cicalese, et al., “Overlaps help: Improved bounds for group testing with interval queries”, Discrete Applied Mathematics, vol. 155, 2007, pp. 288-299.
Cicalese, F., Damaschke, P., Tansini, L., Werth, S.: Overlaps help: Improved bounds for group testing with interval queries. Discrete Applied Mathematics. 155, 288-299 (2007).
Cicalese, Ferdinando, Damaschke, Peter, Tansini, Libertad, and Werth, Soeren. “Overlaps help: Improved bounds for group testing with interval queries”. Discrete Applied Mathematics 155.3 (2007): 288-299.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar