Error-tolerant nonadaptive interval group testing with density-based tests

In interval group testing, all items in the search space are linearly ordered and each of them is either positive or negative. The goal is to identify all positive ones by interval group tests, each asking a query of the type “does a group of consecutive items contain any positive one?” Xu et al. (1...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-05, Vol.815, p.60-68
Main Authors: Chang, Huilan, Chu, Han-Min
Format: Article
Language:English
Subjects:
Density-based group testing
Error-tolerant
Interval group testing
Nonadaptive algorithm
Splice sites detection
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In interval group testing, all items in the search space are linearly ordered and each of them is either positive or negative. The goal is to identify all positive ones by interval group tests, each asking a query of the type “does a group of consecutive items contain any positive one?” Xu et al. (1998) formulated the splice sites identification problem as an interval group testing problem. Nonadaptive and multistage algorithms have been studied (Cicalese et al. 2005, 2007). Motivated by a situation that a large group with a small number of positives may be too sparse so that positives can not be recognized there, we use density-based group tests to deal with interval group testing. Each density-based group test tells whether the proportion of positive items in a group exceeds a given ratio. We provide bounds on the number of density-based tests in an nonadaptive algorithm with error-tolerance.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2020.02.026