MOTIVATION: The choice of probes is an important feature of hybridisation experiments. In this paper we present an algorithm that optimises probes with respect to a training set of sequences based on Shannon entropy as a quality criterion. The practical motivation for our algorithm is oligonucleotide fingerprinting, a method for the simultaneous identification of sequences (cDNA or genomic DNA) by their hybridisation tags according to a set of short probes such as octamers, although the algorithm is of course not restricted to that application. RESULTS: We can show that our method is superior to the selection of probes according to their frequencies, which is a widely used strategy, and to randomly chosen probe sets. The quality of probe sets is assessed by a simulation pipeline that entails the set of probes as a simulation parameter. The performance of probe sets trained on sequences from different organisms shows additionally that probes should be chosen with regard to the organism under analysis. Case studies are presented on how constraints (G+C-content, complexity of the individual probes) influence the selection process. AVAILABILITY: A description of the oligonucleotide fingerprinting pipeline is published on our web-page http://www.molgen.mpg.de/ approximately ag_onf/met.htm. An executable of the algorithm and probe lists designed for human and rodents can be downloaded from the ftp-site ftp://ftp.molgen.mpg.de/pub/mpimg/probe_design/.

We have developed a novel algorithm for cluster analysis that is based on graph theoretic techniques. A similarity graph is defined and clusters in that graph correspond to highly connected subgraphs. A polynomial algorithm to compute them efficiently is presented. Our algorithm produces a clustering with some provably good properties. The application that motivated this study was gene expression analysis, where a collection of cDNAs must be clustered based on their oligonucleotide fingerprints. The algorithm has been tested intensively on simulated libraries and was shown to outperform extant methods. It demonstrated robustness to high noise levels. In a blind test on real cDNA fingerprint data the algorithm obtained very good results. Utilizing the results of the algorithm would have saved over 70% of the cDNA sequencing cost on that data set. 1 Introduction Cluster analysis seeks grouping of data elements into subsets, so that elements in the same subset are in some sense more cl...

MOTIVATION: Massive oligonucleotide hybridization is one of the most promising technologies of functional genome analysis. The critical point is to design appropriate sets of oligonucleotides that can be used effectively in identification by hybridization. RESULTS: Using a genetic algorithm approach, we have attempted to design sets of oligo probes capable of identifying new genes belonging to a defined gene family within a cDNA or genomic library. It is not limited by oligonucleotide length and admits the letter 'N' in the structure of the oligonucleotides selected. One of the major advantages of this approach is the low homology required to identify functional families of sequences with little homology. We have designed the oligonucleotide sets that are most selective for the cDNA clones of transmembrane G protein-coupled receptors (GPCRs), a large family of proteins that form part of a modular system of extracellular signal transduction to the intracellular second messenger pathways. The accuracy of identification has been checked on the EST library containing 713 870 cDNA sequences. A set of 15 oligos between 7 and 14 bases in length has correctly identified 70% of the GPCR cDNA collection sequences with 0.02% false positives. AVAILABILITY: The developed software is available by ftp://ftp.bionet.nsc. ru/pub/biology/ and on the Web page http://www.bionet.nsc. ru/SRCG/Oligoselector/. CONTACT: [email protected]; sebastian. [email protected]