### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P., Cicalese, F., Tansini, L. och Werth, S. (2007) *Overlaps help: Improved bounds for group testing with interval queries*.

** BibTeX **

@article{

Damaschke2007,

author={Damaschke, Peter and Cicalese, Ferdinando and Tansini, Libertad and Werth, Sören},

title={Overlaps help: Improved bounds for group testing with interval queries},

journal={Discrete Applied Mathematics},

issn={0166-218X},

volume={155},

issue={3},

pages={288-299},

abstract={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.
},

year={2007},

keywords={group testing, interval query, non-adaptive strategy, computational molecular biology},

}

** RefWorks **

RT Journal Article

SR Print

ID 26568

A1 Damaschke, Peter

A1 Cicalese, Ferdinando

A1 Tansini, Libertad

A1 Werth, Sören

T1 Overlaps help: Improved bounds for group testing with interval queries

YR 2007

JF Discrete Applied Mathematics

SN 0166-218X

VO 155

IS 3

SP 288

OP 299

AB 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.

LA eng

DO 10.1016/j.dam.2006.07.002

OL 30