title: Efficient non-unique probes selection algorithms for DNA microarray.
abstract: BACKGROUND
  Temperature and salt concentration are very helpful experimental conditions for a probe to hybridize uniquely to its intended target. In large families of closely related target sequences, the high degree of similarity makes it impossible to find a unique probe for every target. We studied how to select a minimum set of non-unique probes to identify the presence of at most d targets in a sample where each non-unique probe can hybridize to a set of targets.
  
  
  RESULTS
  We proposed efficient algorithms based on Integer Linear Programming to select a minimum number of non-unique probes using d-disjunct matrices. Our non-unique probes selection can also identify up to d targets in a sample with at most k experimental errors. The decoding complexity of our algorithms is as simple as O(n). The experimental results show that the decoding time is much faster than that of the methods using d-separable matrices while running time and solution size are comparable.
  
  
  CONCLUSIONS
  Since finding unique probes is often not easy, we make use of non-unique probes. Minimizing the number of non-unique probes will result in a smaller DNA microarry design which leads to a smaller chip and considerable reduction of cost. While minimizing the probe set, the decoding ability should not be diminished. Our non-unique probes selection algorithms can identify up to d targets with error tolerance and the decoding complexity is O(n).
authors: Computer Science Department, the University of Illinois at Springfield, Springfield, IL 62703, USA. pdeng2@uis.edu
authors: Ping
authors: P
authors: Deng
authors: My T
authors: MT
authors: Thai
authors: Qingkai
authors: Q
authors: Ma
authors: Weili
authors: W
authors: Wu
mesh_terms: D000465:Algorithms; D015341:Nucleic Acid Probes / Q000235:genetics*; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*
chemical_list: D015341:Nucleic Acid Probes