PAGE 7 OF 16 Nucleic Acids Research, 2005, Vol. 33, No. 13 e115 listed in the order of their ascending C+G content and the eukaryotes are in the end. The C+G content affects many functional properties of DNA and genes. Therefore, this intrinsic property of genomes was taken into account and used to organize the genomes in analyses and for visualization of results. The lowest C+G content, 26.2%, was for Buchnera sp., and the highest, 65.6%, for M.tuberculosis. The organisms analyzed were chosen to represent different genuses and large variation of environmental growth conditions. The number of genes increases linearly along with genome size, however there are less genes than expected in eukaryotes due to the presence of mosaic genes (i.e. those having exons and introns) that make individual genes larger. In addition, the coding regions of eukaryotes were few hundred bases longer on aver- age than for prokaryotes. All the analyzed small genomes are for intronless prokaryotes. Search for unique and valid oligonucleotides We were looking for unique 25mers with the error threshold k = 4. First, the oligonucleotides were partitioned into three pieces of length 8, which under our partitioning principle leads into locating the occurrences of (3 mod 1) + 1 = 2 of the pieces with at most bk/jc = b4/3c = 1 error, and the single remaining piece with bk/jc 1 = 0 errors (Figure 1). Then, these occurrences were located by using a method reminiscent of the d-neighborhood generation (46). An 8-gram 1-neigh- borhood was generated for each piece xi by enumerating a sufﬁcient set of 8-grams that will contain or be contained in any string z such that ed(xi, z) < 1. An index containing all the locations of all 48 = 65 536 different oligonucleotides with length 8 in the genome was used in ﬁnding fast the occurrences of the generated 8-grams. Next, a two-phase ﬁl- tering method (44) was applied. The surroundings of a given 8-gram occurrence was checked for a complete k-match of x, only if the 8-gram matched xi exactly or if the surroundings contained also an occurrence of an 8-gram belonging to the 1-neighborhood of some other pattern piece. Fast bit-parallel approximate string matching algorithm (48) was used in the ﬁnal stage of checking for a k-match of x. If a match was found, then x was non-unique and the checking process was terminated. If no match was found, x was unique. Figure 6. Distribution of codons in oligonucleotides. Data is shown only for valid oligonucleotides in genome data. Note that yeast, C.elegans and A.thaliana data contain also the flanking 50 and 30 regions.