In this article, we advance a new group testing model \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$GTMIET ( n , d , q ( {k_1} , {k_2} , \ldots , {k_t} ) , e )$$
\end{document} with multiple inhibitor sets and error-tolerant and propose decoding algorithms for it to identify all its positives by using \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( d + k + 1; 2e + 1 )$$
\end{document}-disjunct matrix. The decoding complexity for it is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( {n^m}logn )$$
\end{document}, where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$m = \sum \nolimits_{j = 1}^t {k_j}$$
\end{document}. Moreover, we extend this new group testing to threshold group testing and give the threshold group testing model \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ThGTMIET ( n , d , q ( {k_1} , {k_2} , \ldots , {k_t} ) , u , g , e )$$
\end{document} with multiple inhibitor sets and error-tolerant. By using \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( d + k - l , u;2e + 1 ]$$
\end{document}-disjunct matrix, we propose its decoding algorithms for gap g = 0 and g > 0, respectively. Finally, we point out that the new group testing is the natural generalization for the clone model.
Get full access to this article
View all access options for this article.
References
1.
BonisA.D., and VaccaroU.2003. Constructions of generalized superimposed codes with appli-cations to group testing and conflict resolution in multiple access channels. Theor. Comput. Sci. Ser. A., 306, 223–243.
2.
ChenH.B., DuD.Z., and HwangF.K.2007. An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution. J. Combin. Optim., 14, 121–129.
3.
ChenH.B. and FuH.L.2009. Nonadaptive algorithms for threshold group testing. Discrete Appl. Math., 157, 1581–1585.
4.
ChenH.B., FuH.L., and HwangF.K.2008. An upper bound of the number of tests in pooling designs for the error-tolerant complex model. Optim. Lett., 2, 425–431.
5.
ChungF., GrahamR., and LeightonF.T.2001. Guessing secrets. Electron. J. Combin., 8, 1–25.
6.
DamaschkeP.2006. Treshold group testing. Gen. Theory Inf. Transfer Comb., 4123, 707–718.
7.
DuD.Z., and HwangF.K.2000. Combinatorial Group Testing and Its Applications, 2nd ed. World Scientific, Singapore.
8.
DuD.Z., and HwangF.K.2006. Pooling Design: Group Testing in Molecular Biology. World Scientific, Singapore.
9.
EngelK.1996. Interval packing and covering in the boolean lattice. Combin. Prob. Comput., 5, 373–384.
10.
FarachM., KannanS., KnillE., et al.1997. Group testing problems with sequences in experimental molecular biology, 357–367. In: CarpentieriB., et al., eds. Proceedings of the Compression and Complexity of Sequence. IEEE Press; Piscataway, NJ, USA.
11.
HeY., TianH., ZhangX., et al.2012. Nonadaptive algorithms for threshold group testing with inhibitors and error-tolerance. J. Comput. Biol., 19, 903–910.
12.
HwangF.K., and LiuY.C.2003. Error-tolerant pooling design with inhibitors. J. Comput. Biol., 10, 231–236.
13.
StinsonD.R., and WeiR.2004. Generalized cover-free families. Discrete Math. 279, 463–477.
14.
ThaiM.T., and ZnatiT.2009. On the complexity and approximation of non-unique probe selection using d-disjunct matrix. J. Comb. Optim., 17, 45–53.
