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. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II. Sunderam VS, van Albada GD, Sloot PMA, Dongarra JJ (Eds); Lecture Notes in Computer Science, 3515. Berlin: Springer: 1029-1037.

Konferenzbeitrag | Veröffentlicht | Englisch
 
Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Autor/in
; ;
Herausgeber*in
; ; ;
Abstract / Bemerkung
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.
Erscheinungsjahr
2005
Titel des Konferenzbandes
Computational Science – ICCS 2005. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II
Band
3515
Seite(n)
1029-1037
Konferenz
5th International Conference on Computational Science (ICCS 2005)
Konferenzort
Atlanta, GA
Konferenzdatum
2005-05-22 – 2005-05-25
ISSN
0302-9743
Page URI
https://pub.uni-bielefeld.de/record/1603101

Zitieren

Cicalese F, Damaschke P, Vaccaro U. Optimal group testing strategies with interval queries and their application to splice site detection. In: Sunderam VS, van Albada GD, Sloot PMA, Dongarra JJ, eds. Computational Science – ICCS 2005. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II. Lecture Notes in Computer Science. Vol 3515. Berlin: Springer; 2005: 1029-1037.
Cicalese, F., Damaschke, P., & Vaccaro, U. (2005). Optimal group testing strategies with interval queries and their application to splice site detection. In V. S. Sunderam, G. D. van Albada, P. M. A. Sloot, & J. J. Dongarra (Eds.), Lecture Notes in Computer Science: Vol. 3515. Computational Science – ICCS 2005. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II (pp. 1029-1037). Berlin: Springer. doi:10.1007/11428848_130
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. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II, Sunderam, V. S., van Albada, G. D., Sloot, P. M. A., and Dongarra, J. J. eds. Lecture Notes in Computer Science, vol. 3515, (Berlin: Springer), 1029-1037.
Cicalese, F., Damaschke, P., & Vaccaro, U., 2005. Optimal group testing strategies with interval queries and their application to splice site detection. In V. S. Sunderam, et al., eds. Computational Science – ICCS 2005. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II. Lecture Notes in Computer Science. no.3515 Berlin: Springer, 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. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II, V.S. Sunderam, et al., eds., Lecture Notes in Computer Science, vol. 3515, Berlin: Springer, 2005, pp.1029-1037.
Cicalese, F., Damaschke, P., Vaccaro, U.: Optimal group testing strategies with interval queries and their application to splice site detection. In: Sunderam, V.S., van Albada, G.D., Sloot, P.M.A., and Dongarra, J.J. (eds.) Computational Science – ICCS 2005. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II. Lecture Notes in Computer Science. 3515, p. 1029-1037. Springer, Berlin (2005).
Cicalese, Ferdinando, Damaschke, Peter, and Vaccaro, Ugo. “Optimal group testing strategies with interval queries and their application to splice site detection”. Computational Science – ICCS 2005. 5th International Conference, Atlanta, GA, USA, May 22-25, 2005. Proceedings, Part II. Ed. Vaidy S. Sunderam, Geert Dick van Albada, Peter M. A. Sloot, and Jack J. Dongarra. Berlin: Springer, 2005.Vol. 3515. Lecture Notes in Computer Science. 1029-1037.