CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Overlaps help: Improved bounds for group testing with interval queries

Ferdinando Cicalese ; Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers)) ; Libertad Tansini (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers)) ; Sören Werth
11th International Computing and Combinatorics Conference COCOON 2005, Lecture Notes in Computer Science Vol. 3595 (2005), p. 935-944.
[Konferensbidrag, refereegranskat]

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>1 and s>2. 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=1 and s=2 where optimal strategies were implemented by disjoint queries.



Denna post skapades 2006-08-25. Senast ändrad 2015-02-11.
CPL Pubid: 6413