Development and implementation of a parallel algorithm for the fast design of oligonucleotide probe sets for diagnostic DNA microarrays

摘要

We describe an accurate method for the automatic parallel generation of oligonucleotide probe sets for DNA microarrays. This approach includes a component for high-performance specificity evaluation of designed probes in large data sets. The three main algorithmic components of the method, namely probe preselection, hybridization prediction and probe selection are explained in detail. We introduce new combinatorial techniques for the efficient selection of probe sets of high differentiation capability even from sequence databases of conserved homologous genes. These techniques include the automatic generation of group specific probes as well as the design of excluding probes. A basic prototype has been implemented including a shared memory parallclization. Test runs have been performed on a multiprocessor personal computer with subsets of a small subunit ribosomal ribonucleic acid database, containing very conserved sequence data. The applicability of our program is pointed out by designing a set of oligonucleotide probes that shall allow a comprehensive parallel identification and differentiation of several groups of extremophilic prokaryotes by DNA microarray. The probe set is accessible via the Internet. On applying the parallel version on a dual processor system an efficiency of 80% was achieved.