Overlaps Help: Improved Bounds for Group Testing with Interval Queries
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 axe 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.
Ferdinando Cicalese Peter Damaschke Libertad Tansini Soren Werth
AG Genominformatik, Technische Fakultat, Universitat Bielefeld, Germany School of Computer Science and Engineering, Chalmers University, 41296 Goteborg, Sweden Mathematisches Seminar Bereich 2, University Kiel, 24118 Kiel, Germany
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
935-944
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）