Abstract
Classical group testing is a search paradigm where the goal is the identification of individual positive elements in a large collection of elements by asking queries of the form “Does a set of elements contain a positive one?”. A graph reconstruction problem that generalizes the classical group testing problem is to reconstruct a hidden graph from a given family of graphs by asking queries of the form “Whether a set of vertices induces an edge”. Reconstruction problems on families of Hamiltonian cycles, matchings, stars and cliques on n vertices have been studied where algorithms of using at most 2nlg n,(1+o(1))(nlg n),2n and 2n queries were proposed, respectively. In this paper we improve them to \((1+o(1))(n\lg n),(1+o(1))(\frac{n\lg n}{2}),n+2\lg n\) and n+lg n, respectively. Threshold group testing is another generalization of group testing which is to identify the individual positive elements in a collection of elements under a more general setting, in which there are two fixed thresholds ℓ and u, with ℓ<u, and the response to a query is positive if the tested subset of elements contains at least u positive elements, negative if it contains at most ℓ positive elements, and it is arbitrarily given otherwise. For the threshold group testing problem with ℓ=u−1, we show that p positive elements among n given elements can be determined by using O(plg n) queries, with a matching lower bound.
Similar content being viewed by others
References
Aigner M (1988) Combinatorial search. Wiley, New York
Alon N, Asodi V (2005) Learning a hidden subgraph. SIAM J Discrete Math 18:697–712
Alon N, Beigel R Kasif S, Rudich S, Sudakov B (2004) Learning a hidden matching. SIAM J Comput 33:487–501
Anderson I (1990) Combinatorial designs: construction methods. Ellis Horwood, Chichester
Angluin D, Chen J (2006) Learning a hidden hypergraph. J Mach Learn Res 7:2215–2236
Angluin D, Chen J (2008) Learning a hidden graph using O(log n) queries per edge. J Comput Syst Sci 74:546–556
Beigel R, Alon N, Apaydin MS, Fortnow L, Kasif S (2001) An optimal procedure for gap closing in whole genome shotgun sequencing. In: Proceedings 2001 RECOMB. ACM, New York, pp 22–30
Bouvel M, Grebinski V, Kucherov G (2005) Combinatorial search on graphs motivated by bioinformatics applications: a brief survey. Lect Notes Comput Sci 3787:16–27
Chen HB, Fu HL (2009) Nonadaptive algorithms for threshold group testing. Discrete Appl Math 157:1581–1585
Damaschke P (2006) Threshold group testing. Lect Notes Comput Sci 4123:707–718
Du DZ, Hwang FK (2006) Pooling designs and nonadaptive group testing—important tools for DNA sequencing. World Scientific, Singapore
Grebinski V, Kucherov G (1998) Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discrete Appl Math 88:147–165
Grebinski V, Kucherov G (2000) Optimal reconstruction of graphs under the additive model. Algorithmica 28:104–124
Nagura J (1952) On the interval containing at least one prime number. Proc Jpn Acad 28:177–181
Sorokin A, Lapidus A, Capuano V, Galleron N, Pujic P, Ehrlich SD (1996) A new approach using multiplex long accurate PCR and yeast artificial chromosomes for bacterial chromosome mapping and sequencing. Genome Res 6:448–453
Torney DC (1999) Sets pooling designs. Ann Comb 3:95–101
Author information
Authors and Affiliations
Corresponding author
Additional information
This research is partially supported by NSC 97-2115-M-009-011-MY3.
Rights and permissions
About this article
Cite this article
Chang, H., Chen, HB., Fu, HL. et al. Reconstruction of hidden graphs and threshold group testing. J Comb Optim 22, 270–281 (2011). https://doi.org/10.1007/s10878-010-9291-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-010-9291-0