2-stage fault tolerant interval group testing

摘要: We study the following fault tolerant variant of interval group testing model: Given four positive integers n, p, s, e, determine minimum number questions needed to identify a (possibly empty) set P ⊆ {1, 2,..., n} (|P| ≤ p), under constraints. Questions have form "Is I∩P ≠= O", where I can be any in 2..., n}. are organized s batches non-adaptive (stages), i.e, given batch formulated relying only on information gathered with answers previous batches. Up e erroneous or lies. The is motivated by several applications. remarkably, problem identifying splice sites genome. In particular, such application motivates focus algorithms that some degree and organize few stages, i.e., cases when small, typically not larger than 2. To best our knowledge, we first consider strategies for testing. We completely characterize fully situation provide tight bounds case two strategies. Our differ factor √11/10 p = 1 at most 2 general case.