Abstract
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%.
Original language | English (US) |
---|---|
Pages (from-to) | 2023-2030 |
Number of pages | 8 |
Journal | Annals of Biomedical Engineering |
Volume | 35 |
Issue number | 11 |
DOIs | |
State | Published - Nov 2007 |
Externally published | Yes |
Keywords
- HIV identification
- Integer linear programming
- Optimization
- Virus identification
ASJC Scopus subject areas
- Biomedical Engineering