An optimal cutting-plane algorithm for solving the non-unique probe selection problem

Michelle A. Ragle, J. Cole Smith, Panos M. Pardalos

Research output: Contribution to journalArticle

11 Scopus citations

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 languageEnglish (US)
Pages (from-to)2023-2030
Number of pages8
JournalAnnals of Biomedical Engineering
Volume35
Issue number11
DOIs
StatePublished - Nov 1 2007
Externally publishedYes

Keywords

  • HIV identification
  • Integer linear programming
  • Optimization
  • Virus identification

ASJC Scopus subject areas

  • Biomedical Engineering

Fingerprint Dive into the research topics of 'An optimal cutting-plane algorithm for solving the non-unique probe selection problem'. Together they form a unique fingerprint.

  • Cite this