e115 Nucleic Acids Research, 2005, Vol. 33, No. 13 Our aim was to develop a method for searching unique and valid oligonucleotides or probes for genes so that there is not even a similar (approximate) occurrence in any other location of the whole genome. Thus, for unique oligonucleotides there are no matches present in a genome within certain edit dis- tance. All other oligonucleotides are called redundant. Not all the unique probes are suitable for practical experiments, therefore valid probes have to be distinguished from unique sequences. The Levenshtein edit distance (45) was used as the measure of similarity between two oligonucleotides. Let ed(x, y) denote the Levenshtein edit distance between the strings x and y. Then ed(x, y) is deﬁned as the minimum num- ber of edit operations needed to convert x to y or vice versa, where a single edit operation can either replace, delete or insert a single character. Given an oligonucleotide x and an error threshold k, we deem x to be unique if there is no such other oligonucleotide y that ed(x, y) < k and some occurrence of y does not overlap x. By using probe size 25, we analyzed 17 complete genomes representing a wide range of both prokaryotic and eukaryotic organisms. It was possible to ﬁnd a large number of unique oligonucleotides for all the genomes. To avoid cross- hybridization when using the probes, edit distance of four was used, i.e. only such sequences were accepted for which related sequences with at most 20 matches were present. We deﬁne unique sequences as those, which do not have matches within allowed edit distance. As valid oligos are called when they are unique and they in addition meet a number of criteria for avoiding adverse effects of self-annealing and have high enough Tm. More than 92% of all the genes in the investigated genomes contained valid oligonucleotides, and thus were probeable. Extensive statistical tests were performed to char- acterize the properties of oligonucleotides. These segments were relatively evenly distributed in genes except for the beginning and end, which were somewhat overrepresented. In addition to distributions within genes, also the effects on codon and amino acid usage were tested. Although the major- ity of codons and residues had expected distributions in major- ity of the genomes some interesting trends were apparent. Table 1. Properties of studied genomes and oligonucleotides PAGE 2 OF 16 MATERIALS AND METHODS Genomes The 17 genomes used in the tests were taken from the NCBI database (Table 1). When analyzing coding sequences (CDSs) in eukaryotes, the coding areas were concatenated with 100 nt extensions on both sides. Oligos used in laboratories are often directed to 50 regions of genes. Many genes in genomes of prokaryotes are spaced so closely that the downstream and upstream regions of adjacent genes overlap. Therefore, it was possible to analyze the extensions only in the larger eukaryotic genomes. Overview of the search method The method for locating unique oligonucleotides is a modi- ﬁcation of a central pattern partitioning principle in approx- imate string matching. We will use the notation x [ y to denote the concatenation of x and y, and the notation x y means that x is a substring of y. The best current methods for indexed approximate string matching (46,47) are essentially based on the following pattern partitioning principle: If ed(x, y) < k and x = x1 [ x2 [ ··· [ xj, then for some index i, where 1 < i < j, there exists string z, such that ed(z, xi) < bk/jc and z y. A direct consequence of the above principle is that if the oligonucleotide x is partitioned into j pieces x1, x2, . . ., xj, then, for any oligonucleotide y, ed(x, y) < k only if the oligo- nucleotide y contains at least one of the pieces x1, x2, . . ., xj with at most bk/jc errors. This permits using the following steps to check whether a given oligonucleotide x is unique: (i) Partition x into j pieces x1, x2, . . ., xj. (ii) Find all locations in the genome where one of the pieces x1, x2, . . ., xj occurs with at most bk/jc errors. (iii) Check the surroundings of each pattern piece occurrence for a k-match of the complete oligonucleotide x. (iv) If no such k-match of x is found that does not overlap with x itself, x is unique. Organism Buchnera sp. B.burgdorferi C.acetobutylicum S.solfataricus H.pylori B.subtilis A.aeolicus Thermotoga maritime A.fulgidus E.coli N.meningitidis S.typhimurium A.tumefaciens M.tuberculosis C.elegans A.thaliana S.cerevisiae Classa Prg S F A Prd/e F Bh Bh A Prg Prb Prb Pra Ac E E E Genome size (106) C+G (%) CDS Unique oligos (106) Valid oligos (106) Genome Unique oligos (106) Valid oligos (106) CDS Unique oligos/gene Valid oligos/gene 0.64 0.91 3.94 2.99 1.67 4.21 1.55 1.86 2.17 4.63 2.27 4.81 2.84 4.4 95.2 116.7 12.1 27.5 28.9 31.7 36.6 39.8 44.5 43.8 46.5 49.6 52.1 53.4 53.5 60.4 66.0 41.0 42.9 38.9 0.4 0.586 1.812 1.696 1.107 2.945 1.183 1.44 1.619 3.182 1.31 3.202 1.81 2.116 8.53 9.61 6.105 0.296 0.416 1.428 1.317 0.715 2.121 0.741 0.958 0.944 2.058 0.739 1.986 0.944 0.936 6.36 6.912 4.672 0.343 0.5 1.411 1.452 0.963 2.6 1.115 1.341 1.53 2.82 1.15 2.788 1.512 1.584 2.128 2.232 4.466 0.265 0.367 1.118 1.128 0.626 1.873 0.699 0.889 0.893 1.824 0.659 1.741 0.806 0.749 1.391 1.315 3.387 708 689 494 571 707 718 778 780 673 742 647 697 665 505 516 374 968 525 489 389 444 456 517 487 519 392 480 365 432 347 223 385 269 741 aA, Archae; Ac, Actinobacteria; Bh, hyperthermophilic bacterium; E, eukaryote; F, Firmicute; Pr, Probacteria; S, Spirochete.