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

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers)) ; Ferdinando Cicalese ; Libertad Tansini ; Sören Werth
Discrete Applied Mathematics (0166-218X). Vol. 155 (2007), 3, p. 288-299.
[Artikel, refereegranskad vetenskaplig]

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 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>1 and s>2 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=1 and 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>2. Anyway, the remaining gaps between the current upper and lower bounds for any fixed s>2 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.

Nyckelord: group testing, interval query, non-adaptive strategy, computational molecular biology

Denna post skapades 2007-03-07. Senast ändrad 2015-02-11.
CPL Pubid: 26568