Selection based heuristics for the non-unique oligonucleotide probe selection problem in microarray design

In order to accurately measure the gene expression levels in microarray experiments, it is crucial to design unique, highly specific and highly sensitive oligonucleotide probes for the identification of biological agents such as genes in 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 introduce original deterministic greedy heuristics for finding near minimal non-unique probe sets. The heuristics, guided by selection functions defined over a probe set, decide at each moment which probes are the best to be included in, or excluded from, a candidate solution. Our methods substantially outperform the only two known greedy heuristics in the literature for the non-unique probe selection problem. We also obtained results that are very close to, and sometimes better than, those of the current state-of-the-art methods for the non-unique probe selection problem, namely integer linear programming and optimal cutting-plane approaches.