Efficient non-unique probes selection algorithms for DNA microarray.
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).
Deng
Ping
P
Computer Science Department, the University of Illinois at Springfield, Springfield, IL 62703, USA. pdeng2@uis.edu
Thai
My T
MT
Ma
Qingkai
Q
Wu
Weili
W
D000465:Algorithms; D015341:Nucleic Acid Probes / Q000235:genetics*; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*
D015341:Nucleic Acid Probes