New construction of error-correcting pooling designs from singular linear spaces over finite fields
- PDF / 323,544 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 50 Downloads / 176 Views
New construction of error-correcting pooling designs from singular linear spaces over finite fields Gang Wang1
· You Gao2
Accepted: 17 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The group testing problem is that we are asked to identify all the defects with the minimum number of tests when given a set of n items with at most d defects. In this paper, as a generalization of Liu et al.’s construction in the paper (Liu and Gao in Discret Math 338:857–862, 2015), new pooling designs are constructed from singular linear spaces over finite fields. Then we make comparisons with Liu et al.’s construction in the aspects of parameters of pooling designs. By choosing appropriate parameters in our pooling designs, the performance of test efficiency in our pooling designs is better than that given by Liu et al. Finally, the analysis of parameters in our pooling designs is provided. Keywords Pooling designs · m z -Disjunct matrices · Test efficiency · Singular linear spaces · Finite fields Mathematics Subject Classification 05B20 · 51E26
1 Introduction The group testing problem is that we are asked to identify all the defects with the minimum number of tests when given a set of n items with at most d defects. Each of the tests is on an arbitrary subset of n items, called a pool. There are two possible outcomes of each test on the subset: the test outcome is positive if the pool contains at least one defect, while the test outcome is negative if the pool does not contain any defect. The group testing has important applications in many areas, especially in molecular biology (Li et al. 2010). The objective of group testing is influenced by
B
Gang Wang [email protected]
1
School of Mathematical Sciences, Tianjin Normal University, Tianjin 300387, People’s Republic of China
2
College of Science, Civil Aviation University of China, Tianjin 300300, People’s Republic of China
123
Journal of Combinatorial Optimization
minimizing the number of tests, limiting number of pools, limiting pool sizes and tolerating a few errors. A group testing algorithm is called non-adaptive if all the tests must be specified without knowing the outcomes of other tests. A non-adaptive group testing can be characterized by a binary matrix, called pooling design, whose rows are indexed by pools and columns are indexed by items with the entry (i, j) is 1 if and only if the jth item is contained in the ith pool. However, the test outcomes may contain some errors in the group testing process because of a variety of reasons. The mathematical model of s e -disjunct matrix is introduced for error tolerant in the group testing. A binary matrix M is said to be s e -disjunct if given any s + 1 columns of M with one designated, there are e + 1 rows with a 1 in the designated column and 0 in each of the other s columns. Furthermore, an s e -disjunct matrix is fully s e -disjunct if it is not s1e1 -disjunct whenever s1 > s or e1 > e. Pooling designs can reduce the cost greatly and have many appl
Data Loading...
