Name
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=2 and s=3 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==3. Anyway, the remaining gaps between the current upper and lower bounds for any fixed s=3 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 | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.dam.2006.07.002 | Discrete Applied Mathematics |
Keywords | Field | DocType |
subset q intersect p,new bounds converge,unknown distinguished subset p,improved bound,overlaps help,lower bound,fixed number,new idea,interval query,special cases p,positive element,improved upper bound,group testing,new query scheme | Ordered set,Discrete mathematics,Combinatorics,Database query,Disjoint sets,Computer science,Upper and lower bounds,Contrast (statistics),Group testing,The Intersect | Journal |
Volume | Issue | ISSN |
155 | 3 | Discrete Applied Mathematics |
ISBN | Citations | PageRank |
3-540-28061-8 | 3 | 0.41 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ferdinando Cicalese | 1 | 450 | 48.20 |
| Peter Damaschke | 2 | 471 | 56.99 |
| Libertad Tansini | 3 | 8 | 4.36 |
| Sören Werth | 4 | 12 | 2.42 |