PAGE 3 OF 16 Organism Buchnera sp. B.burgdorferi C.acetobutylicum S.solfataricus H.pylori B.subtilis A.aeolicus T.maritima A.fulgidus E.coli N.meningitidis S.typhimurium A.tumefaciens M.tuberculosis C.elegans A.thaliana S.cerevisiae Table 2. General properties of studied genomes and oligonucleotides Classa Prg S F A Prd/e F Bh Bh A Prg Prb Prb Pra Ac E E E Genome Unique oligos/gene 609 588 384 489 615 634 733 727 635 658 568 607 556 378 129 87 708 Valid oligos/gene Invalid oligos/gene 469 432 304 380 400 457 460 481 371 425 326 379 296 179 84 51 537 495 547 593 449 531 413 471 443 434 504 523 514 613 750 1380 1424 1054 Nucleic Acids Research, 2005, Vol. 33, No. 13 e115 Number of genes 564 850 3672 2968 1566 4100 1521 1846 2407 4289 2025 4595 2722 4187 16522 25694 6306 Average gene length 987.3 1002.9 921.0 852.4 954.5 893.5 954.7 948.6 829.2 953.6 872.7 917.1 933.1 952.9 1288 1499.5 1414.7 Probeable genes Probeable genes (%) 564 847 3659 2648 1529 4095 1515 1832 2379 4218 1866 4509 2714 4132 15673 24392 6013 100 99.6 99.6 89.2 97.6 99.9 99.6 99.2 98.8 98.3 92.1 98.1 99.7 98.7 94.9 94.9 95.34 aA, Archae; Ac, Actinobacteria; Bh, hyperthermophilic bacterium; E, eukaryote; F, Firmicute; Pr, Probacteria; S, Spirochete. Figure 1. Principle of the oligonucleotide analysis program. The oligos are searched by sliding a window of 25 positions along the analyzed sequence. The 25mer is partitioned to three 8mers and a single nucleotide. 1-neighborhoods (difference of one character allowed) are constructed for each piece and com- pared to the precomputed index of the locations of all 8mers in the investigated data (coding regions or complete genome). Two-phase filtering program and fast bit-parallel approximate string matching algorithm are used to identify the uniqueness of the 25mers. This basic approach can be improved in certain circum- stances. Let di denote the number of errors permitted when searching for the piece xi. Previous methods typically assign di = bk/jc for each piece xi, as discussed above. But we note that it is possible to set di = bk/jc for (k mod j) + 1 pieces and di = bk/jc 1 for the rest, if any left, without missing a single k-match of x. This is because if no piece xi is found inside y with at most di errors, then the total number of errors needed in converting y into x is at least (d1 + 1) + (d2 + 1) + · · · + (dj + 1) = j + d1 + d2 + · · · + dj = j + [( k mod j) + 1] · bk/jc + [ j (k mod j) 1] · (bk/jc 1) = j + j · bk/jc j + Figure 2. Effects of edit distance and the use of criteria on the number of unique and valid oligonucleotides in A.thaliana data. The analysis was done for unique (black) and valid (red) oligos on coding region as well as for unique (green) and valid (blue) oligos in the whole genome. (k mod j) + 1 = j · bk/jc + (k mod j) + 1 = k + 1 and thus ed(x, y) > k. Our method is equal to the basic method when (k mod j) + 1 = j and leads into an improvement in all other cases. The algorithm was implemented on C++ and run either in a normal PC with sufﬁcient RAM or in a Linux cluster of 10 virtual parallel computers. Selection criteria for oligonucleotides Primers can be utilized for many purposes and therefore in addition to uniqueness they have to meet other criteria depend- ing on the intended use. The oligonucleotides designed here were primarily aimed for gene expression studies in micro- arrays. The typical length of such oligonucleotides is 25,