Reconstructing a Hamiltonian Cycle by Querying the Graph: Application to DNA Physical Mapping

Vladimir Grebinski Gregory Kucherov 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper studies four mathematical models of the multiplex PCR method of genome physical mapping described in \cite{Sorokin1}. 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.
Type de document :
Article dans une revue
Discrete Applied Mathematics, Elsevier, 1998, 88 (1-3), pp.147-165
Liste complète des métadonnées

https://hal.inria.fr/inria-00098545
Contributeur : Publications Loria <>
Soumis le : lundi 25 septembre 2006 - 17:03:14
Dernière modification le : mardi 6 mars 2018 - 17:40:58

Identifiants

  • HAL Id : inria-00098545, version 1

Collections

Citation

Vladimir Grebinski, Gregory Kucherov. Reconstructing a Hamiltonian Cycle by Querying the Graph: Application to DNA Physical Mapping. Discrete Applied Mathematics, Elsevier, 1998, 88 (1-3), pp.147-165. 〈inria-00098545〉

Partager

Métriques

Consultations de la notice

154