conference paper
Overlaps Help: Improved Bounds for Group Testing with Interval Queries
published
Ferdinando
Cicalese
author
Peter
Damaschke
author
Libertad
Tansini
author
Soeren
Werth
author
441317
department
66100
department
11th Annual International Conference on Computing and Combinatorics (COCOON 2005)
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.
2005
eng
Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)
0302-974310.1007/11533719_94
935-944
F. Cicalese, et al., “Overlaps Help: Improved Bounds for Group Testing with Interval Queries”, <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>, Lecture Notes in Computer Science, 3595, 2005, pp.935-944.
Cicalese F, Damaschke P, Tansini L, Werth S (2005) <br />In: Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Lecture Notes in Computer Science, 3595. 935-944.
F. Cicalese, P. Damaschke, L. Tansini, and S. Werth, in <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>, <strong>2005</strong>, p. 935-944.
Cicalese F, Damaschke P, Tansini L, Werth S. Overlaps Help: Improved Bounds for Group Testing with Interval Queries. In: <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>. 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. <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>, 935-944. doi:10.1007/11533719_94
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).
F. Cicalese, et al., Overlaps Help: Improved Bounds for Group Testing with Interval Queries, in <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>, Lecture Notes in Computer Science, 3595 (2005), p. 935-944.
Cicalese, F., Damaschke, P., Tansini, L., and Werth, S. (2005). “Overlaps Help: Improved Bounds for Group Testing with Interval Queries” in <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em> Lecture Notes in Computer Science, 3595 935-944.
Cicalese, Ferdinando, Damaschke, Peter, Tansini, Libertad, and Werth, Soeren. “Overlaps Help: Improved Bounds for Group Testing with Interval Queries”. <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>. 2005. Lecture Notes in Computer Science, 3595. 935-944.
Cicalese, F.; Damaschke, P.; Tansini, L.; 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, ). S. 935-944.
<div style="text-indent:-25px; padding-left:25px;padding-bottom:0px;">Cicalese, Ferdinando, Damaschke, Peter, Tansini, Libertad, and Werth, Soeren. 2005. “Overlaps Help: Improved Bounds for Group Testing with Interval Queries”. In <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>, 935-944. Lecture Notes in Computer Science, 3595.</div>
<div style="text-indent:-25px; padding-left:25px;padding-bottom:0px;">Cicalese, F., Damaschke, P., Tansini, L. & Werth, S. (2005). Overlaps Help: Improved Bounds for Group Testing with Interval Queries (Lecture Notes in Computer Science, 3595). <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em> (S. 935-944). Gehalten auf der 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). doi:10.1007/11533719_94.</div>
Cicalese, F., et al., 2005. Overlaps Help: Improved Bounds for Group Testing with Interval Queries. In <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>. Lecture Notes in Computer Science, 3595. pp. 935-944.
<div style="text-indent:-25px; padding-left:25px;padding-bottom:0px;">Cicalese, F., Damaschke, P., Tansini, L., & Werth, S. (2005). Overlaps Help: Improved Bounds for Group Testing with Interval Queries. <em>Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005)</em>, 935-944. doi:10.1007/11533719_94</div>
Cicalese F, Damaschke P, Tansini L, Werth S (2005) <br />Overlaps Help: Improved Bounds for Group Testing with Interval Queries. <br />In: Proc. 11th Annual International Conference on Computing and Combinatorics (COCOON 2005). Lecture Notes in Computer Science, 3595, 935-944.
23088672011-08-05T09:03:18Z2018-07-24T12:59:56Z