{'fraction_non_alphanumeric': 0.031080434088732845, 'fraction_numerical': 0.012607724225981488, 'mean_word_length': 4.722602739726027, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 1, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Genome-wide selection of unique and valid oligonucleotides

Functional genomics methods are used to investigate the huge amount of information contained in genomes. Numerous experimental methods rely on the use of oligo- or polynucleotides. Nucleotide strand hybridization forms the underlying principle for these methods. For all these techniques, the probes should be unique for analyzed genes. In addition to being unique for the studied genes, the probes should fulfill a large number of criteria to be usable and valid. The criteria include for example, avoidance of self-annealing, suitable melting temperature and nucleotide composition. We developed 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. By using probe size 25, we analyzed 17 complete genomes representing a wide range of both prokaryotic and eukaryotic organisms. More than 92% of all the genes in the investigated genomes contained valid oligonucleotides. Extensive statistical tests were performed to characterize the properties of unique and valid oligonucleotides. Unique and valid oligonucleotides were relatively evenly distributed in genes except for the beginning and end, which were somewhat overrepresented. The flanking regions in eukaryotes were clearly underrepresented among suitable oligonucleotides. In addition to distributions within genes, the effects on codon and amino acid usage were also studied.


INTRODUCTION
The complete genome of a large number of organisms including bacteria, archaea and eukaryotes have been determined along with the human genome. Currently, there are some 230 bacterial and archaeal, and 34 finished eukaryal genomes.
Genomes contain overwhelming amount of information, which can be investigated with numerous experimental and computational techniques. Many experimental methods rely on the use of oligo-or polynucleotides. Nucleotide strand hybridization-preferably with unique probes-forms the underlying principle for these methods. PCR technology, the workhorse of molecular biology, utilizes oligonucleotides as primers to copy and amplify genetic material. Gene expression studies such as Southern and northern blotting and more advanced SAGE and microarrays also utilize oligonucleotides. Gene function can be modulated by short oligonucleotides either by antisense technology or by RNA interference (RNAi). For all these techniques, the probes ought to be unique for analyzed genes.
Oligonucleotides for an organism can be identified from complete genomes. If working with mRNA only, genes and flanking regions have to be analyzed, whereas if genomic DNA is the target, the probes should be unique for the whole genome. In addition to being unique for the studied genes, the probes have to fulfill a large number of criteria, which vary due to the use of probes. These criteria include, for example, the avoidance of self-annealing, suitable melting temperature (T m ) and nucleotide composition. A number of methods have been developed for primer design [e.g. (1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13), http://www-genome. wi.mit.edu/genome_software/other/primer3.html; for a review see (14)]. MEDUSA shows visually the location of the primer pairs (15). Simulated annealing and Lagrangian relaxation algorithms have been used to design oligonucleotides to study microbial communities (16). Organisms can be identified with proper oligos (17). Methods for oligonucleotide selection and probe production for microarrays have also been developed (18)(19)(20)(21)(22)(23)(24)(25)(26)(27)(28)(29)(30)(31). Numerous methods have been developed to predict antisense oligonucleotides (32)(33)(34)(35)(36) and RNAi (37)(38)(39)(40)(41). Probes for full gene synthesis have to be specially designed (42). Oligos can be designed also for protein interaction studies (43). When degenerate oligonucleotides are used for cloning orthologues and paralogues, primers have to be specially designed. The properties of genome-wide unique oligonucleotide studies have not been published, although some methods for the search of such strings have been presented (44). The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact journals.permissions@oupjournals.org 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 distance. 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 defined as the minimum number 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 find a large number of unique oligonucleotides for all the genomes. To avoid crosshybridization 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 define 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 T m . More than 92% of all the genes in the investigated genomes contained valid oligonucleotides, and thus were probeable. Extensive statistical tests were performed to characterize 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 majority of codons and residues had expected distributions in majority of the genomes some interesting trends were apparent.

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 5 0 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 modification of a central pattern partitioning principle in approximate 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 = x 1 [ x 2 [ ··· [ x j , then for some index i, where 1 < i < j, there exists string z, such that ed(z, x i ) < bk/jc and z y.
A direct consequence of the above principle is that if the oligonucleotide x is partitioned into j pieces x 1 , x 2 , . . ., x j , then, for any oligonucleotide y, ed(x, y) < k only if the oligonucleotide y contains at least one of the pieces x 1 , x 2 , . . ., x j 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 x 1 , x 2 , . . ., x j . (ii) Find all locations in the genome where one of the pieces x 1 , x 2 , . . ., x j 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. This basic approach can be improved in certain circumstances. Let d i denote the number of errors permitted when searching for the piece x i . Previous methods typically assign d i = bk/jc for each piece x i , as discussed above. But we note that it is possible to set d i = bk/jc for (k mod j) + 1 pieces and d i = bk/jc À 1 for the rest, if any left, without missing a single k-match of x. This is because if no piece x i is found inside y with at most d i errors, then the total number of errors needed in converting y into x is at least (d 1 + 1) 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 sufficient 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 depending on the intended use. The oligonucleotides designed here were primarily aimed for gene expression studies in microarrays. The typical length of such oligonucleotides is 25,       which has been used also on commercial chips by Affymetrix. The valid oligonucleotides were defined by the following conditions. They may include at most 12 A, 12 T, 10 C or 10 G nucleotides, and no window of 8 nt includes more than 6 A, 6 T, 4 C or 4 G nucleotides. Further, the oligonucleotides include at most 6 successive A, 6 successive T, 5 successive C or 5 successive G nucleotides. An inverse complementary oligonucleotide of an oligonucleotide can match at most six symbols from the beginning of an oligonucleotide. These criteria were used to avoid self-annealing, self-end annealing and to provide high enough T m . The distance threshold was four edit operations, i.e. no more than four errors were allowed.

RESULTS AND DISCUSSION
There is a great demand for functional oligonucleotides for a large spectrum of techniques. The oligonucleotides should be unique to allow specific and reliable binding. Genome-wide analyses are routine in many fields and therefore the probes utilized should not hybridize with any other genes or parts of genome. A method to determine, analyze and identify unique oligonucleotides from complete genomes was developed. The method was applied to the analysis of 17 complete genomes (Table 1). The Archaeoglobus fulgidus and Sulfolobus solfataricus represented Archae, Aquifex aeolicus and Thermotoga maritima hyperthermophilic bacteria, Escherichia coli, Salmonella typhimurium and Buchnera sp. for Probacteria gamma subdivision, Agrobacterium tumefaciens for alpha subdivision, Neisseria meningitidis for beta subdivision and Helicobacter pylori for delta/epsilon subdivision. Of the Firmicutes included were Bacillus subtilis and Clostridium acetobutylicum, and of Actinobacteria, Mycobacterium tuberculosis was included. Borrelia burgdorferi exemplified Spirochete. The Eukaryotes included were Caenorhabditis elegans, a nematode, Saccharomyces cerevisiae, baker's yeast for fungi, and Arabidopsis thaliana for plants.
The genomes contained 564-25 694 genes and spanned 0.6-117 Mb. Some general properties of the genomes and oligonucleotides are in Tables 1 and 2. The organisms are 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 average 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-neighborhood was generated for each piece x i by enumerating a sufficient set of 8-grams that will contain or be contained in any string z such that ed(x i , z) < 1. An index containing all the locations of all 4 8 = 65 536 different oligonucleotides with length 8 in the genome was used in finding fast the occurrences of the generated 8-grams. Next, a two-phase filtering 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 x i 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 final 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 5 0 and 3 0 regions. Different computer setups were used for calculations and analysis. The genomes of prokaryotes as well as of S.cerevisiae were processed on a single PC with 1 GB RAM. The use of large enough memory facilitated storage of the complete genome and avoidance of excessive I/O operations. The two eukaryotes with larger genomes, C.elegans and A.thaliana, were processed in parallel on a Linux cluster of 10 PCs. The processing time was $3 days for A.thaliana and somewhat <2 days for C.elegans. It is thus feasible to search unique and valid probes for any organism.

Unique and valid probes
The analysis was divided into two parts to obtain full picture of the properties and distribution of unique and valid oligos in a single strand and in both strands. We determined unique and valid oligos both for CDS regions (in eukaryotes together with 5 0 and 3 0 extensions of 100 bp) and for the complete genome. If not otherwise stated, the results refer to genome-wide analysis. The proportion of unique oligonucleotides varied between 18.2 and 59.4% (25.3 and 83.6%) depending on the organism being smaller for the larger genomes. The corresponding values for valid oligos are 3.5 and 52.5 (18.2 and 52.3%). The numbers in parentheses are for CDS regions. Unique and valid probes were found for at least 92% of the genes, which is in agreement with the theoretical calculations based on the size of the genome and density of the genes (data not shown). The number of redundant probes exceeded significantly the number of valid oligos for all the eukaryotes analyzed as well as A.tumefaciens, N.meningitidis and M.tuberculosis. The total number of valid oligos per gene was high, the average varying from 51 to 537. The use of annealing and composition criteria clearly reduced the number of valid oligos compared to unique ones. Naturally, the use of more stringent edit distance has similar effect ( Figure 2). C+G content has no direct effect on the number or ratios of valid and redundant oligos.

Nucleotide distribution
To analyze the properties of the oligos, the distribution of nucleotides within the unique and valid oligonucleotides It is of interest that the curves pass through almost a single point when traversing from T to C ratio. The major differences to the parity rules is the genome of A.fulgidus, which is the only one where the ratios for A and T, and C and G are not close to each other. The use of criteria to choose for valid oligos biases the distribution in B.burgdorferi, which has quite low C+G content. This seems to be related to nucleotide composition because the distribution of Buchera sp., which has the lowest C+G content among the analyzed genomes, has also slightly biased U-shaped distribution. When looking at the actual differences compared to normal distributions, the biggest change can be seen in C.acetobutylicum and the other genomes with extreme C+G values ( Figure 3E and F). The criteria for valid oligos significantly reduce the number of oligos (Table 2). Valid/unique oligo ratio is from 0.47 to 0.79. Valid/invalid oligo ratio for genome data is from 0.036 to 1.11.
Further analysis of the nucleotide numbers in oligonucleotides indicated that the distribution in the majority of bacterial and archaeal genomes was as expected (Figure 4). The major exceptions were M.tuberculosis and C.acetobutylicum. Of these, M.tuberculosis has the highest C+G content among the analyzed genomes. It has more than expected number of oligonucleotides with 4-11 A, or 5-10 T, or 6-7 C, or 5-8 G bases among the valid oligos for genome data. On the other hand, oligonucleotides with large numbers of C or G are in fact underrepresented.
The distributions of yeast, C.elegans and A.thaliana are all very biased. Common to all these is the underrepresentation of small numbers of nucleotides in oligos, overrepresentation usually in the range 3-8 and again underrepresentation in the range 9-19 nt. The actual borders of these patterns vary between nucleotide types and organisms. Interestingly, the B location of peaks is shifted towards smaller base counts for A and T, and towards higher counts for C and G when compared to bacteria and archaea. The Z-values are very high for the eukaryotic organisms.

Valid and redundant oligonucleotides
The distribution of the unique, valid and redundant oligonucleotides within the genes and flanking regions were estimated by calculating Z-values. The flanking regions of eukaryotic genes are numbered as 0 and 8 in Figure 5A, where coding regions have been divided into seven equal partitions. If there was uneven number of nucleotides, the middlemost (4th) partition was shorter. Both the 5 0 and 3 0 flanking sequences are highly underrepresented among the valid oligonucleotides. The reason is that these regions contain common and therefore conserved patterns involved in transcription and translation start and stop. In all these genomes, the last section contains slightly reduced proportion of valid oligos. The bacterial and arhaeal genomes have quite unbiased distribution throughout the genes. It has been a general trend to select probes, for example for antisense and microarray applications from the beginning of genes. The first and last sections in eukaryal genomes are somewhat surprisingly overrepresented among the unique and valid oligos. As a conclusion, oligonucleotides can be selected almost equally well from all the sections within coding region whereas in eukaryotes the flanking regions contain much less than expected of valid and unique oligonucleotides.
When looking at the ratio of the valid and invalid oligos ( Figure 5C and D), the same trends are apparent. In all the organisms, the graphs have remarkably flat distribution except for sections 0 and 8. The section 7 is universally somewhat decreased in all the prokaryal genomes. Sections 1 and 7 contain only slightly higher ratios than sections 2-6 for eukaryotes.

Effects on codon usage
The effect on the coding properties of the valid oligonucleotides was studied by calculating the Z-values for the distribution of each codon ( Figure 6). The expected codon frequencies We compared further the Z-values for all codons ( Figure 7A-D). Synonymous codons are known to have strong bias. Codon usage has effect, for example, on the translation. Highly expressed genes contain mainly those codons for which there are abundant tRNAs. The codon usage varies between organisms. There were no general trends for the usage of codons.
When looking at the codon usage within the seven sections of genes, the majority of the codons in the majority of organisms have a normal distribution. The distribution is almost equal for the majority of codons in each section. However, certain patterns are visible. The largest, eukaryal genomes have the highest Z-scores, especially A.thaliana, which had significant bias in many places. Also C.elegans and S.cerevisiae have biased distribution to sections, but not that often and generally the Z-values are smaller than for A.thaliana, which is clearly the largest of the studied genomes. Clear examples of C+G-rich codons for alanine and glycine are A.tumefaciens and M.tuberculosis, which have significantly less codons containing C or G in the third position, although these organisms have the highest overall C+G content. Also S.typhimurium is biased towards not having G at the third position in codon for alanine. C.acetobutylicum has strong bias in a number of codons, and S.solfataricus and A.fulgidus in some individual cases. The genomes of prokaryotes have less biased distribution. Usually, the eukaryotes clearly favor certain triplets when synonymous codons appear.

Effects on amino acid level
The 25mers from coding regions were further studied on amino acid level. Depending on the location within codons, the oligo-encoded sequence matched with either 7 or 8 amino acids in the protein sequence. The encoded amino acids of the oligonucleotides were compared to general amino acid compositions in each organism. Z-values ( Figure 8) indicate strong bias from general pattern. As already seen in the codon usage, C.acetobutylicum and M.tuberculosis along with B.burgdorferi have the largest Z-values. Otherwise, the bacterial genomes have rather even distribution. The yeast, nematode and plant genomes have the largest variation and there are in fact only a few residue types that have normal distribution in these organisms.
When looking at the effect of C+G content on the amino acid bias, it is evident that most of the residues have normal distribution. However, there is quite linear correlation between the decrease in alanine and glycine along increased C+G content and opposite effect in lysine. The distribution within the genes was further investigated by calculating the distribution within eight equally sized gene segments (Figure 9).
Certain residues such as C, D, H, M, Q and S have very equal distribution in all sections. G has generally somewhat pronounced underrepresentation in the middle of the sequence when compared to the termini. Also in this data, the organisms that have greatest bias in the other features are biased, namely the three eukaryotes and C.acetobutylicum, and M.tuberculosis of prokaryotes.

CONCLUSIONS
A new method for searching unique and valid oligonucleotides from complete genomes was developed. Despite the exhaustive analysis approach, genomes of any size could be analyzed. The presented method can be modified to permit other probe lengths and/or error thresholds. This may affect the run time, which is dependent on the ratio between the permitted number of errors and the probe length. When processing even larger genomes, such as the human genome, one should take into account the fact that using a too large error threshold may lead to a situation where practically all oligonucleotides are non-unique. Unique and valid oligos can clearly be found from any part of the gene, however the termini are overrepresented. The use of the criteria for valid oligos changes the overall properties of the oligonucleotides. By changing the criteria, the method could be easily modified for different purposes, e.g. to search for oligos functional in RNAi technology (37).