Optimal group testing strategies with interval queries and their application to splice site detection

Cicalese F, Damaschke P, Vaccaro U (2005)
In: COMPUTATIONAL SCIENCE - ICCS 2005, PT 2. 3515. SPRINGER-VERLAG BERLIN: 1029-1037.

Conference Paper | Published | English

No fulltext has been uploaded

Author
; ;
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.
Publishing Year
ISSN
PUB-ID

Cite this

Cicalese F, Damaschke P, Vaccaro U. Optimal group testing strategies with interval queries and their application to splice site detection. In: COMPUTATIONAL SCIENCE - ICCS 2005, PT 2. Vol 3515. SPRINGER-VERLAG BERLIN; 2005: 1029-1037.
Cicalese, F., Damaschke, P., & Vaccaro, U. (2005). Optimal group testing strategies with interval queries and their application to splice site detection. COMPUTATIONAL SCIENCE - ICCS 2005, PT 2, 3515, 1029-1037.
Cicalese, F., Damaschke, P., and Vaccaro, U. (2005). “Optimal group testing strategies with interval queries and their application to splice site detection” in COMPUTATIONAL SCIENCE - ICCS 2005, PT 2, vol. 3515, (SPRINGER-VERLAG BERLIN), 1029-1037.
Cicalese, F., Damaschke, P., & Vaccaro, U., 2005. Optimal group testing strategies with interval queries and their application to splice site detection. In COMPUTATIONAL SCIENCE - ICCS 2005, PT 2. no.3515 SPRINGER-VERLAG BERLIN, pp. 1029-1037.
F. Cicalese, P. Damaschke, and U. Vaccaro, “Optimal group testing strategies with interval queries and their application to splice site detection”, COMPUTATIONAL SCIENCE - ICCS 2005, PT 2, vol. 3515, SPRINGER-VERLAG BERLIN, 2005, pp.1029-1037.
Cicalese, F., Damaschke, P., Vaccaro, U.: Optimal group testing strategies with interval queries and their application to splice site detection. COMPUTATIONAL SCIENCE - ICCS 2005, PT 2. 3515, p. 1029-1037. SPRINGER-VERLAG BERLIN (2005).
Cicalese, F, Damaschke, P, and Vaccaro, U. “Optimal group testing strategies with interval queries and their application to splice site detection”. COMPUTATIONAL SCIENCE - ICCS 2005, PT 2. SPRINGER-VERLAG BERLIN, 2005.Vol. 3515. 1029-1037.
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