Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping

This paper studies four mathematical models of the multiplex PCR method of genome physical mapping described in Sorokin et al. (1996). The models are expressed as combinatorial group testing problems of finding an unknown Ham iltonian cycle in the complete graph by means of queries of different type. For each model, an efficient algorithm is proposed that matches asymptotic ally the information-theoretic lower bound. (C) 1998 Elsevier Science B.V. All rights reserved.