noncoding regions are the major part of eukaryote genomes , and most of them are believed to evolve neutrally ( kimura 1983 ) . under this assumption , we expect that the frequency of a particular short oligonucleotide , or dna word , of 10 bp or shorter should be primarily determined through accumulation of neutral mutations , and the total set of frequencies of all dna words of certain length should follow some simple statistical rules . oligonucleotide frequencies of one genome can provide a useful mechanism of genome comparison ( karlin 2005 ) , including phylogeny reconstruction ( takahashi et al . most frequently , such comparisons are based on a dinucleotide composition model ( karlin and mrazek 1997 ; gentles and karlin 2001 ) or on self - organizing maps ( abe et al . 2003 ) . we created a series of statistical models predicting the frequencies of word of up to 4 nt in a genome . we retrieved all available complete eukaryote and prokaryote genomes , constructed such models for them , and compared the actual word frequencies with those predicted by the models to determine the discrepancy . here , we present a database , called genome composition database ( gcd ) , which shows how accurately each genome can be approximated by a model . the unique point of this database is that it allows to compare compositional complexity of genomes and to analyze over- or underrepresentation of particular oligonucleotides . 2007 ) , ensembl ( http://uswest.ensembl.org/ ; flicek et al . 2012 ) , university of california  santa cruz ( http://genome.ucsc.edu/ ; fujita et al . 2011 ) , flybase ( http://flybase.org/ ; mcquilton et al . 2012 ) , and wormbase ( http://www.wormbase.org/ ; harris 2010 ) . genome sequences of a total of 1,228 species ( 101 eukaryotes , 1,043 eubacteria , and 84 archaea , as of june 2010 ) were used to construct the database . for every genome , we created a series of five composition models : uniform ( composition of a , c , g , and t are set to be all 25% ) , mononucleotide , dinucleotide , trinucleotide , and tetranucleotide . each composition model is based on the total size and word frequencies of an actual genome . we use both dna strands to perform the word counting , so the number of g bases is always same with number of c , same for a and t , and each dna word has the same frequency with its reversed complementary counterpart . among the 16 dinucleotides , there are 12 that differ from their reversed complementary dinucleotide and 4 that are identical to their reversed complementary one ( cg , gc , at , and ta ) . therefore , the first group of dinucleotides can be described with six frequencies ( 12/2 ) and the second  with four . subtracting one , and adding the genome size , we obtain ten parameters for the dinucleotide model . in case of trinucleotide frequencies , none of the trinucleotides are identical to their reversed complementary counterpart , so the model has 4/2 = 32 parameters . in tetranucleotide case , there are 16 tetranucleotides that are identical to their reversed complementary counterparts , so the tetranucleotide model has ( 4  16)/2 + 16 = 136 parameters . for a genome g of total length m and a dna word w , a composition model can be used to compute p(w ) , which is the probability of observing w at any particular position in the genome . for example , the uniform composition model gives(1)where l is the length of w. the mononucleotide composition model predicts(2)where wi is the ith nucleotide of w , f(x ) is the observed frequency of x in the genome sequence , and c(x ) is the complementary sequence to x. using the same principle , p(w ) from dinucleotide , trinucleotide , and tetranucleotide composition models can be computed . the model expectation of the frequency of word w in both strands of the modeled genome is then given as follows:(3 ) then , we can define the deviation of the observed frequency from the expected frequency:(4 ) because each of the composition models assumes independence of different genome positions from each other , e(w ) follows the binomial distribution , and its variance can be computed as follows:(5 ) the standard deviation of e(w ) is its square root . we then can define the relative abundance of w , under this particular model , as follows:(6 ) this r(w ) is 0 for dna words , occurring in the genome with exactly the same frequency , as predicted by the composition model . r(w ) is positive when the actual frequency is larger than expected by the model . in such cases , we describe that w is overrepresented in the genome , according to this model . when the actual frequency is smaller than expected by the model , r(w ) is negative , and w is underrepresented . now we can summarize the overall magnitude of over- or underrepresentation of all dna words of length l in the genome ( using a particular composition model of choice ) as follows:(7)where w is the set of all dna words of length l and   because r is the standard deviation of a sample of all r(w ) for a particular word length l , the unit of r is the same with that of r(w ) , which is e(w ) ( standard deviation of the word frequency , predicted by the model ) . for each w , re(w ) gives the relative number of occurrences of w , which would make w averagely rare or abundant . r is computed for a particular genome , composition model , and l and summarizes the ability of the composition model to predict the frequencies of words of length l in the genome . large r implies that many w 's have large absolute values of r(w ) , which means that their actual frequencies are far from those expected by the model . thus , a large value of r signifies that the model 's ability to describe the actual genome is poor . a good composition model has small value of r , with r being 0 for the perfect model . an example of such perfect model is the l - bp composition model used to predict the frequencies of words of the same length l bp or shorter . for instance , the dinucleotide composition model has the exact information about dinucleotide frequencies , so it gives perfect predictions for 1-bp or 2-bp word frequencies , resulting in r value of 0 . for the longer words , r is typically much larger than 0 for nonrandom sequences . on the other hand , when a random sequence is modeled using any composition model , the actual variances of the word frequencies are the same with the variances predicted by the model ; therefore , r is close to 1 in this case ( approaching 1 as the sequence becomes longer ) . this is also the case for semirandom sequences , where the deviation from uniform randomness is at most as complex ( controlled by at most as many parameters ) as the model used to analyze the sequence . for example , a semirandom gc - biased sequence can be accurately modeled by the nucleotide composition model , or any more complex model , but not by the uniform composition model . the r values obtained with the uniform composition model for such sequence are much larger than 1 , whereas other models still produce r close to 1 . figure 1 illustrates this by showing the example histograms of relative abundances for all words of length 8 in the human genome , using five different models . the strange bimodal - looking shape of the uniform model histogram results from the extreme depletion of cpg dinucleotide in mammalian ( including human ) genomes . any 8-bp word containing cpg will appear as strongly underrepresented when comparing the actual frequencies with those predicted by the uniform model . so , all such words contribute to the left peak on the histogram , whereas words without cpg form the other peak , in agreement with the model . histograms of relative abundances of all oligonucleotides of 8 bp in human genome , according to the five composition models . the words placed to the left of the line are underrepresented and to the right  overrepresented . we computed r for all five composition models for available complete genomes , both eukaryotes and prokaryotes . we then extracted unusually rare and unusually abundant words , which we define as those having |r(w)| > r. these dna words , together with the corresponding statistics , are available for viewing and downloading at the gcd online . r value comparison for selected species note.this table compares the r values of e. 
 coli , yeast , plant , fruit fly , fish , lizard , and mouse , respectively , for each of the five models we used , based on words of 8 bp . next , we analyzed the spacing patterns of individual dna words in complete genomes . looking at all occurrences of a particular dna word in the genome , we can extract the distances between the genomic locations of every two neighboring occurrences and use this set of distances as a spacing data set for this particular word . sample parameters ( mean , standard deviation , skewness , and kurtosis ) are computed for such data set . the mean distance approximately equals to the genome size divided by total number of occurrences , so it correlates with the reciprocal of the word frequency . skewness shows whether extremely unusual spacing values for this word tend to be large or small . kurtosis shows if the word tends to form clusters and the density of those clusters relative to the distance between them . taking a particular parameter for all words of length l furthermore , selecting only subset of dna words with parameters falling into particular ranges , we can extract interesting dna words . in order to verify the models and better understand the parameters , we constructed a range or semirandom sequences using a random sequence generator ( kryukov k , unpublished data ) . each semirandom sequence was based on particular real genome used as template ( e.g. , the human genome ) : it had the same size with the template genome , and it imitated n - bp composition of the template genome , with n ranging from 1 to 4 . we used genomes of five species as templates : human , anolis carolinensis ( lizard ) , xenopus tropicalis ( frog ) , oryzias latipes ( fish ) , and drosophila melanogaster ( fruit fly ) . figure 2 shows the comparison of r values for 101 eukaryote genomes used in this study , as well as representative prokaryote genomes , computed for 5 bp oligonucleotides . such r values represent how well different composition models can predict 5-bp composition of the genome . supplementary figure 1 ( supplementary material online ) shows comparison of all prokaryote genomes included in this study . r values of five composition models are displayed as differently colored areas . as can be seen mammals are compositionally more complex than nonmammal vertebrates , land vertebrates are more complex than fishes , and fishes are more complex than most invertebrates and plants , which are still more complex than fungi and protists . compositional genome complexity of prokaryotes , represented by r values , is comparable with that of fungi . comparison of r values based on oligonucleotides of 5 bp and all five composition models . ( a ) eukaryote genomes ( all available in public databases by october 2010 ) . figure 3 shows the average r values for different groups of organisms , with standard deviation . under all five composition models , statistically significant difference is observed between the r values of mammals and nonmammal vertebrates ( mann  whitney p < 0.001 , see supplementary table 1 , supplementary material online for test results ) . interestingly , r values of invertebrates are close to those of plants and significantly higher than those of fungi , protists , or prokaryotes ( archaea and eubacteria ) . in terms of r values , average r values for different groups of organisms , with standard deviations , using five different composition models . tables 2 and 3 show the partial lists of under- and overrepresented words of 10 bp in human genome , using tetranucleotide composition model . the complete lists of under- and overrepresented words , for every of the included genomes , for each of the five composition models , and for dna words of up to 10 bp for eukaryotes and 8 bp for prokaryotes , are available at the gcd online . both the actual and the expected frequency are given for both dna strands combined , so each word 's frequency is identical with that of its reversed complementary counterpart ( given in parentheses ) . underrepresented oligonucleotides of 10 bp , example from human genome note.showing ten most underrepresented oligonucleotides , according to the tetranucleotide composition model . both the actual and the expected frequency are given for both dna strands combined , so each word 's frequency is identical with that of its reversed complementary counterpart ( given in parentheses ) . overrepresented oligonucleotides of 10 bp , example from human genome note.showing ten most overrepresented oligonucleotides , according to the tetranucleotide composition model . other than the reporting the general compositional complexity , the gcd can be used to compute the distances between the composition vectors of various complete genomes and submitted sequences ( similar to the method taken by takahashi et al . we used this tool to analyze three classes of human sequences : random sample from the human genome , conserved sequences of unknown function , and conserved functionally important sequences . although sequences from these three classes are all found in the human genome , they have different nature and evolutionary history , allowing interesting comparison . the uce data set ( human  mouse  rat ultraconserved elements , 481 sequence , 126 kbp in total , bejerano et al . human microrna ( mirna ) seed sequences ( 1,100 sequences from mirbase , 7.7 kbp in total , kozomara and griffiths - jones 2011 ) were used as functionally important conserved sequences . figure 4a shows the average euclidean distances between the composition vectors obtained from randomly sampled human sequence and composition vectors of complete vertebrate genomes . each sample was chosen to have the same number of sequences and average sequence length with the uce data set : 481 sequences , 262 bp each . di- , tri- , and tetranucleotide composition vectors are used for comparison . as expected , primate genomes are the closest to human sample , and more diverged species show progressively larger distances , with some fluctuations . euclidean distances between composition vectors ( oligonucleotide frequencies ) of sample data sets and complete vertebrate genomes for three composition models ( dinucleotide , trinucleotide , and tetranucleotide ) . one thousand samples were used , where each sample consisted of 481 sequences of 262 bp each ( for a total size of each sample same with the uce data set ) , taken from the random locations in the complete human genome . ( b ) the composition of the uce data set is compared with that of complete vertebrate genomes . ( c ) the composition of human mirna seed sequences is compared with that of complete vertebrate genomes . the compositional distances between the uce and the complete vertebrate genomes appear to be relatively uniform among vertebrates and much larger than those for the random human sample . interestingly , these sequences appear to be compositionally close to lizard , fish , and frog . figure 4c shows the compositional distances between human mirna sequence data set and complete vertebrate genomes . platypus and the fishes are compositionally the closest to this data set . to further investigate the differences between these three data sets , we computed the average distances by combining the genomes into four groups ( fig . 5 ) . 5a ) , while much more uniformity can be seen for uce and mirna seed data sets ( fig . 5b and c ) . average compositional distance ( euclidean distances between the composition vectors ) between sample data sets and complete genomes grouped into four groups . panels ( a , b , and c ) correspond to panels ( a , b , and c ) of figure 4 . figure 6 shows the plots for the pairs of spacing parameters , taken for 8 bp oligonucleotides for six species  human , lizard , fish , fruit fly , yeast , and escherichia coli . although the interpretation is difficult , more structure can be seen in the plots of more complex organisms . plots of the spacing distribution parameters for six species , based on oligonucleotides of 8 bp . different columns show plots for different pairs of parameters , from left to right : mean spacing ( x axis ) versus standard deviation ( y axis ) , mean ( x ) versus skewness ( y ) , mean ( x ) versus log(kurtosis ) ( y ) , standard deviation ( x ) versus skewness ( y ) , standard deviation ( x ) versus log(kurtosis ) ( y ) , and skewness ( x ) versus log(kurtosis ) ( y ) . each dot in the plot represents a particular 8 bp dna word , so 48 words constitute the data set in each case . figure 7 shows spacing plots for four random genomes ( generated using human genome as a template ) , the complete actual human genome and the repeat - masked version of the human genome . repeat - masked is included because complexity is often associated with repetitive sequences . in case of the those elements correspond to the groups of dna words containing different number of gc . with gc contents being the only parameter for constructing the sequence , dna words with the same number of gc will have exactly same compositional properties , blurred only by randomness of the sequence . in case of  hs random 2  similar grouping happens , this time depending on number of cpg each particular word may contain . going into more complex semirandom sequence , the discreteness becomes less clear , and the plots are getting closer to that for the real human genome . still significant difference remains between the plots of semirandom and real sequences and very little difference between the plots of repeat - masked and the complete human genome . plot of the spacing distribution parameters for semirandom sequences , compared with the real human genome , as well as repeat - masked one . based on oligonucleotides of 10 bp . semirandom genomes 1 , 2 , 3 , and 4 are constructed using 1- , 2- , 3- , and 4-bp composition of the actual human genome . the gcd provides a convenient measure of relative complexity of various genomes from statistical point of view . a genome is compositionally simple if its composition can be accurately described by a simple model . a set of r values for various word length and models can tell us how complex a particular genome is ? as figure 2 shows , r values become smaller with the increase of model complexity  as expected , a more complex model can describe genome composition more accurately , which results in smaller discrepancy . we observe that , generally speaking , r values are related to the general complexity of the organism . remarkably , even tetranucleotide compositional models are unable to give good predictions of 5-bp composition in case of complex genomes , particularly for mammals and land vertebrates . figure 3 confirms that compositional complexity of a genome is in good correlation with general complexity of the organism . compositional discrepancy r computed with different composition models seems to be useful as a measure of compositional complexity of the genome . the extremely rare and extremely abundant sequences , as shown in tables 2 and 3 , suggest the possible mechanisms of creating compositional complexity . the most underrepresented 10 bp dna words ( using tetranucleotide composition model ) seem to be found on the boundary of mononucleotide repeats , particularly poly - a to poly - t boundary ( words 1 , 2 , 4 , 6 , 7 , 8 , 9 , 10 in table 2 ) also poly - a to poly - c ( words 3 and 5 in table 2 ) . this means that such boundary is much less common , than suggested by the 4-bp composition . among the top overrepresented words , there are poly - a ( word 5 in table 3 ) , dinucleotide repeats ( words 1 and 2 in table 3 ) , as well as fragments of sequence  gcctgtaatcccagc ( words 3 , 4 , 6 , 7 , 8 , 9 in table 3 ) , which has about 800,000 occurrences in the human genome compared with the expected number of about 7,00010,000 . this sequence being unusual is already reported by valle ( 1993 ) ; however , no explanation for the cause was given . figure 4 shows the compositional distances between three sequence data sets ( human sample , uce , and mirna seeds ) and vertebrate genomes . although in all three cases , the sequences are contained in the human genome , the compositional distances of those sequences to various genomes show very different pictures . the random sample behaves as expected  the compositional distance is increasing with the increase of divergence from human . however , uce and mirna seed data sets show more or less uniform compositional distances from various vertebrate genomes . this suggests that those sequences became conserved before the emergence of mammals . in case of mirna seed sequences , the composition distances to all vertebrate genomes are more or less uniform , suggesting those sequences were fixed much earlier than the emergence of vertebrates . composition of the uce and mirna seed sequences is frozen and represents the composition of the ancestoral genome , at the time where the fixation occurred . the compositional distance from the current day vertebrates is larger for mirna seed data set because the mirna fixation occurred much earlier , so larger compositional distance exists between the ancestoral genome and current day genomes . thus , this allows us to discuss the composition of premammal vertebrate genome ( in case of uce data set ) and early animal genome ( in case of mirna seeds ) . oligonucleotide spacing patterns , summarized as sample parameters and displayed as scatterplots ( figs . 6 and 7 ) , provide a further interesting view into the compositional complexity . it is apparent that the human genome is very different from the semirandom sequences that imitate only some compositional properties of the actual genome . however , the spacing scatterplots for the repeat - masked human genome looks similar to those of the complete genome and different from those based on the semirandom sequences . it remains to be seen whether the apparent complexity results from the isochore structure of the mammalian genomes ( bernardi et al . 1985 ) , the online gcd provides the means of comparing the compositional complexity of various complete genome and extracting unusual dna words . the composition parameters computed using five models , as well as histograms , are available . also spacing patterns , summarized as parameter histograms and 2d scatterplots , in addition that database features a facility for submitting a sequence data set and performing composition analysis and comparison with various complete genomes . compositional models that we used in this study only utilize the word frequencies as parameters . the natural next challenge is to design an integrated composition model , which would be based on both frequencies and spacing patterns . such model would better approximate the genome and thus would allow focusing more closely on the real source of complexity . supplementary figure 1 and table 1 are available at genome biology and evolution online ( http://www.gbe.oxfordjournals.org/ ) .
eukaryote genomes contain many noncoding regions , and they are quite complex . to understand these complexities , we constructed a database , genome composition database , for the whole genome composition statistics for 101 eukaryote genome data , as well as more than 1,000 prokaryote genomes . 
 frequencies of all possible one to ten oligonucleotides were counted for each genome , and these observed values were compared with expected values computed under observed oligonucleotide frequencies of length 14 . 
 deviations from expected values were much larger for eukaryotes than prokaryotes , except for fungal genomes . 
 mammalian genomes showed the largest deviation among animals . 
 the results of comparison are available online at http://esper.lab.nig.ac.jp / genome - composition - database/.