.png){kind=icon}
Return
An optimal cutting-plane algorithm for solving the non-unique probe selection problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s10439-007-9374-y.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 provably 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%.
Keywords:
optimization
virus identification
HIV identification
integer linear programming
Journal
IF:
5.4
Papers:
6.3K
Citations:
1.4W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSave
Palladium-Catalyzed C–H Activation: Mass Spectrometric Approach to Reaction Kinetics in Solution
OAAI
OAAIShareSaveShareSave
View more