Learning a Hidden Matching

We consider the problem of learning a matching (i. e. , a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0. 32(n/2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

Authors

• Noga Alon
• Richard Beigel
• Simon Kasif
• Steven Rudich
• Benny Sudakov

Keywords

• DNA
• Sequences
• Genomics
• Bioinformatics
• Upper bound
• Mathematics
• Assembly
• Testing
• Biological system modeling
• Adaptive algorithm
• Whole-genome Sequencing
• Lower Bound
• High Probability
• Family Size
• Test Tube
• Number Of Tests
• Isomorphism
• Perfect Match
• Pair Of Points
• Algorithm For Problem
• Whole Genome Shotgun
• Pair Of Elements
• Projective Space
• Matching Problem
• Single Edge
• Color Categories
• Deterministic Case
• Virtual Point
• J. Craig Venter Institute
• Pieces Of Size
• Set Of Chemicals
• Family Of Subsets
• Number Of Experiments
• Shotgun Sequencing