An optimal cutting-plane algorithm for solving the non-unique probe selection problem.
The non-unique probe selection problem consists of selecting oligonucleotide probes for use in hybridization experiments in which target viruses or bacteria are to be identified in biological samples. The presence or absence of these targets is determined by observing whether selected probes bind to their corresponding sequences. The goal is to select a probe set that is able to uniquely identify targets while containing a minimal number of probes. This paper contributes the first exact method for finding optimal solutions to the non-unique probe selection problem within practical computational limits, without the a priori elimination of candidate probes. Previously published methods have employed heuristics to find approximate solutions that are not probably optimal, and as a result, no knowledge has been obtained regarding the quality of those solutions relative to optimality. We demonstrate that our approach consistently finds an optimal solution to the non-unique probe selection problem within 10 min, and is capable of reducing the number of probes required over state-of-the-art heuristic techniques by as much as 20%.
Ragle
Michelle A
MA
Department of Industrial and Systems Engineering, University of Florida, 303 Weil Hall, Gainesville, FL 32611, USA. raglem@ufl.edu
Smith
J Cole
JC
Pardalos
Panos M
PM
D000465:Algorithms; D019295:Computational Biology / Q000379:methods; D015342:DNA Probes / Q000737:chemistry* / Q000235:genetics; D004279:DNA, Viral / Q000032:analysis* / Q000737:chemistry / Q000235:genetics; D015497:HIV-1 / Q000737:chemistry / Q000235:genetics; D015498:HIV-2 / Q000737:chemistry / Q000235:genetics; D006801:Humans; D009841:Oligonucleotides / Q000032:analysis* / Q000737:chemistry / Q000235:genetics; D012367:RNA, Viral / Q000032:analysis* / Q000737:chemistry / Q000235:genetics; D013997:Time Factors
D015342:DNA Probes; D004279:DNA, Viral; D009841:Oligonucleotides; D012367:RNA, Viral