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

Vladimir Grebinski, Gregory Kucherov

Research output: Contribution to journalArticlepeer-review

61 Citations (Scopus)

Abstract

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 Hamiltonian cycle in the complete graph by means of queries of different type. For each model, an efficient algorithm is proposed that matches asymptotically the information-theoretic lower bound.

Original languageEnglish
Pages (from-to)147-165
Number of pages19
JournalDiscrete Applied Mathematics
Volume88
Issue number1-3
DOIs
Publication statusPublished - 9 Nov 1998
Externally publishedYes

Keywords

  • Algorithms
  • Asymptotic complexity
  • Combinatorial group testing
  • Genome physical mapping

Fingerprint

Dive into the research topics of 'Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping'. Together they form a unique fingerprint.

Cite this