An Evolutionary Approach to the Non-unique Oligonucleotide Probe Selection Problem

Wang L., Ngom A., Gras R., Rueda L.

2nd International Conference on Bio-Inspired Models of Network, Information and Computing Systems, Budapest, Hungary, 10 - 13 December 2007, vol.5410, pp.143-162 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 5410
  • City: Budapest
  • Country: Hungary
  • Page Numbers: pp.143-162
  • Middle East Technical University Affiliated: No


In order to accurately measure the gene expression levels in microarray experiments, it is crucial to design unique, highly Specific and sensitive oligonucleotide probes for the. identification of biological agents such as genes ill a sample. Unique probes are difficult to obtain for closely related genes such as the known strains of HIV genes. The non-unique probe. selection problem is to select a probe set that. is able to uniquely identify targets in a biological sample, while containing a minimal number of probes. This is an NP-hard problem. We define a probe selection function that allows to decide. which are the best probes to include in or exclude from a candidate probe set. We then propose a new deterministic greedy heuristic that uses the selection for solving the non-unique probe selection problem. Finally, we combine the selection function with an evolutionary method for finding near minimal non-unique probe sets. When used on benchmark data sets, our greedy method outperforms current greedy heuristics for non-unique probe selection in most instances. Our genetic algorithm also produced excellent results when compared to advanced methods introduced in the literature for the non-unique probe selection problem.