Cicalese Ferdinando, Damaschke Peter, Vaccaro Ugo
Int J Bioinform Res Appl. 2005;1(4):363-88. doi: 10.1504/IJBRA.2005.008441.
Given an ordered set of n items and an unknown subset P of up to p positive elements, we want to identify P by asking the least number of queries 'does Q intersect P?' where Q must consist of consecutive elements. This Interval Group Testing problem arises in the context of splice site detection in genes. We study algorithms that operate in a few stages where queries chosen depending on previous answers, are performed in parallel. We obtain tight bounds for two-stage strategies. Finally, we get results for any number of stages and positives.
给定一组有序的n个项目以及一个最多包含p个正元素的未知子集P，我们希望通过询问最少数量的“Q与P相交吗？”这样的查询来识别P，其中Q必须由连续元素组成。这个区间分组测试问题出现在基因剪接位点检测的背景中。我们研究在几个阶段运行的算法，在这些阶段中，根据先前的答案选择的查询是并行执行的。我们得到了两阶段策略的精确界限。最后，我们得到了任意阶段数和正元素数量的结果。
