metagenomics is an 
 emerging area of   genome research that allows culture - independent , functional , 
 and    sequence - based studies of microbial communities in environmental samples .
whole - genome 
 shotgun ( wgs ) sequencing has been applied to most of the metagenomic projects [ 16 ] .
these projects have 
 unveiled remarkable information on microbial genomics and also brought an 
 unprecedentedly comprehensive and clearer picture of microbial communities . in 
 the wgs sequencing approach , random sampling of dna fragments of all microbes that 
 form a community in an environmental sample
the individual dna fragments 
 are sequenced and then assembled into genomes by using computing techniques . 

however , a fundamental limit of wgs sequencing is that only the genomes of 
 high - abundance species can be completely or near - completely assembled   due to the requirement of multiple overlapping fragments for a 
 confident assembly . in one of the prominent metagenomic studies conducted by 
 venter et al .
, about 1  gb of dna sequences has been successfully sequenced from 
 sargasso sea samples .
this study has clearly indicated the existence of far 
 more diverse microbial communities than previously thought .
most of the 
 environmental genomes sequenced to date contain only few high - abundance species 
 but many low - abundance species in the communities that account for a large 
 portion of the total genome size of an environmental sample .
the presence of large 
 amount of dna fragments from the low - abundance species poses a problem for 
 assembling genomes . in order to infer the biological functions of a microbial 
 community from sequences , a process named 
binning  is used to group these 
 unassembled dna sequence fragments and small contigs into biologically 
 meaningful  bins ,  such as phylogenetic groups .
these include chisel system 
 [ 9 , 10 ] , metaclust [ 4 , 11 ] , tetra [ 12 , 13 ] , phylopythia , and the combination of oligonucleotide frequency and som .
the chisel system helps binning the sequences according to the 
 identification , characterisation , and comparative analysis of taxonomic and 
 evolutionary variations of enzymes .
the remaining above - listed tools use the 
 method of analysing nucleotide composition of sequences that is considered to have 
 the potential of working well for the binning process in wgs sequencing .
metaclust computes different dna signatures followed by the use of 
 a clustering algorithm to assign sequences into bins .
tetra bins the 
 species - specific sequences by the use of tetranucleotide - derived z - score 
 correlations .
phylopythia uses a supervised - learning approach where it trains a 
 multiclass support vector machine ( svm ) classifier using all the known genome 
 sequences in the existing database then assigns the unknown environmental 
 sequences to the closest clade in the selected taxonomic level .
this method has 
 been demonstrated to be able to classify most dna sequence fragments with high 
 accuracy .
however , considering the current amount of known genomes which is far 
 less than 1% of the entire microbial genomes , it is reasonable to assume that the currently available training data 
 is insufficient to represent all the extremely diverse microbial genomes for 
 supervised - learning methods .
the combination of oligonucleotide frequency and the well - known 
 unsupervised learning method self - organising map ( som ) was used by abe et al .   to explore genome signatures .
they used the di- , tri- , and 
 tetranucleotide frequencies as the training features of som to cluster the 1  kb 
 and 10  kb dna sequence fragments derived from 65 bacteria and 6 eukaryotes . 

clear species - specific separations of sequences were obtained in the 10  kb 
 fragment tests .
their results showed that the combination of oligonucleotide 
 frequency and som can be used as a powerful tool to cluster or bin the dna 
 sequence fragments after wgs sequencing . in order to 
 successfully bin the dna sequence fragments , using an appropriate genome 
 signature as the training feature is important . in recent years , researchers 
 have found that , due to oligonucleotide frequency bias in various prokaryotic 
 genomes , the oligonucleotide frequency can be used as a possible genome 
 signature .
the di- , tri- , and tetranucleotide frequencies , which are the frequencies using two , three , and four nucleotides respectively , have been well studied .
karlin et al . [ 16 , 17 ] has shown the 
 compositional bias of the di- and tetranucleotide contents of 15 prokaryotic 
 genomes .
found that 80% of pseudomonas 
 putida kt2440 genome have a similar bias in gc contents and di- and 
 tetranucleotide contents .
.   showed that the tetranucleotide frequency has a higher 
 discriminatory power than gc content and used it for the assignment of genomic 
 fragments to the taxonomic group .
in addition , sandberg et al .   employed a bayesian approach to classify the short sequences and 
 found that the classification accuracy increases with a higher - order 
 oligonucleotide frequency .
above - mentioned papers provide evidences that there 
 is a trend of using oligonucleotide frequency as prokaryotic genome signature , rather 
 than the gc content .
thus , high - order oligonucleotide frequency may also be an 
 appropriate training feature for binning dna sequence fragments by unsupervised 
 clustering methods .
since the combination 
 of oligonucleotide frequency and som appears as a promising binning strategy 
 that can be further explored , we focus in this paper on improving the training 
 features and the clustering algorithm . in abe
's work , there was no systematic way of comparing the quality of the som 
 results .
we tested the traditional clustering evaluation measures ( recall , precision , 
 and f - measure ) and discovered the inadequacy of using them for examining the 
 similarity of phylogenetic levels .
therefore , we introduce a method to 
 quantitatively measure and assess the results of clustering dna sequence 
 fragments from a collection of species . in the investigation of evaluating 
 suitable training features
, we attempt to compare results for the di- , tri- , 
 and tetranucleotide frequencies as well as the pentanucleotide frequency ( the 
 frequency usage of five nucleotides ) to test if higher - order oligonucleotide 
 frequency yields better binning of dna sequence fragments .
we also study the 
 effectiveness and efficiency of the combination of oligonucleotide frequency 
 and som by employing alternative clustering algorithms .
we compare som with a 
 variant of it called growing self - organising map ( gsom ) , which has been 
 successfully applied in several different applications [ 2025 ] including microarray clustering .
these comparisons allow us to suggest a better compositional binning 
 strategy for wgs sequencing using the method of combining oligonucleotide 
 frequency and som - based clustering algorithm .
this paper is organized as follows : section 2.1 gives a brief 
 introduction to the som and gsom clustering algorithms ; section 2.2 proposes a 
 method of measuring inseparable species when dna sequence fragments are 
 clustered ; section 2.3 describes the procedures 
 of preparing the three 
 datasets used in this paper , and the data preprocessing step for preparing the 
 input vectors ; and section 2.4 shows the details of the algorithm settings and 
 the experiment set up for repeatability of the experiments .
section 3 presents the results of 
 comparing the four orders of oligonucleotide frequencies and the comparison 
 between som and gsom ; finally , section 4 gives the discussion , conclusion , and 
 future work .
growing self - organising 
 map ( gsom ) [ 27 , 28 ] is an extension of self - organising 
 map ( som ) .
gsom is a dynamic som which overcomes the weakness of a static map 
 structure of som .
this is achieved by projecting the high - dimensional 
 data onto a two- or three - dimensional feature map with lattice structure where 
 every point of interest in the lattice represents a neuron or a node in the 
 map .
the mapping preserves the data topology , so that similar samples can be 
 found close to each other on the 2d/3d feature map .
the som training 
 consists of three phases : initialisation phase , ordering phase , and fine - tuning 
 phase .
the following parameters are determined in this phase : 

 the map 
 topology ( either rectangular or hexagonal);the number 
 of nodes which is the resolution of the map;the weight 
 vector initialization of nodes;the 
 width / height ( or aspect ) ratio of the map.the user determines the 
 first two parameters and generally principle components analysis ( pca ) is used 
 for setting the last two parameters .
the weight vectors are initialised by the 
 first two principle vectors of the inputs and the aspect ratio of the map is 
 determined based on the ratio of magnitudes of the first two principle 
 components . in the ordering and fine - tuning phases ,
winner ,  which has the smallest 
 euclidean distance to the presented input , is identified .
the weight vector of 
 the winner and its neighbouring nodes are updated by(1)w(t+1)=w(t)+h[x(k)w(t)],where w(t ) 
 is the weight vector of the node at time t , x(k ) is the kth input vector ( w , xd where d is the dimensionality of data ) ,  is the learning rate and h is the neighbourhood kernel function . 

the map 
 topology ( either rectangular or hexagonal ) ; the number 
 of nodes which is the resolution of the map ; the weight 
 vector initialization of nodes ; the 
 width / height ( or aspect ) ratio of the map .
gsom employs the same 
 weight adaptation and neighbourhood kernel learning as som , but has a global 
 parameter of growth named growth threshold ( gt ) 
 that controls the resolution of the map .
the growth threshold is defined as 
 ( 2)gt=dln(sf),where sf is the user defined spread factor with 0 
 representing minimum growth ( coarsest resolution ) and 1 representing maximum 
 growth ( finest resolution ) .
there are three phases 
 in the gsom training : initialisation phase , growing phase , and smoothing phase . 
 in the initialisation phase ,
the gsom is initialised with a minimum single 
  lattice grid  depending on whether the rectangular or hexagonal topology is 
 chosen . due to the small number of nodes in the beginning of training ,
the 
 weight vector initialisation has less effect on the clustering quality and 
 these weights will be corrected quickly in the growing phase . during the 
 growing phase , every node has an accumulated error counter and the counter of 
 the winner ( ewinner ) is 
 updated by ( 3)ewinner(t+1)=ewinner(t)+x(k)wwinner(t).if the winner is at the 
 boundary of the current map and ewinner exceeds gt , new nodes will be added 
 to the surrounding vacant slots of the winner . in the case when ewinner exceeds gt and the winner is not a boundary 
 node , ewinner is evenly 
 distributed outwards to the winner 's neighbouring nodes . the smoothing phase is 
 for fine - tuning the weights of nodes and no new node will be added to the map .
the 
 shape of gsom represents the hidden data structure better than som that leads 
 to better identifiable clusters.new 
 nodes are added to the necessary regions while keeping the order of nodes . 
 therefore , neither pca nor ordering phase is required in the training.fewer nodes at 
 the beginning of the training leads to the speed   improvement . 
 
the 
 shape of gsom represents the hidden data structure better than som that leads 
 to better identifiable clusters .
new 
 nodes are added to the necessary regions while keeping the order of nodes . 

fewer nodes at 
 the beginning of the training leads to the speed   improvement . in our preliminary test ,
the well - known f - measure , which computes both recall and 
 precision into a single index from a contingency table , was used to evaluate 
 the clustering results . however , after examining the cluster contents , it is 
 apparent that , for binning applications , f - measure does not provide sufficient 
 insight and description of ambiguities in terms of phylogenetic relationships ( refer 
 to section 3 ) .
more specifically , one would expect phylogenetically - close 
 groups as highly likely to be ambiguous , but f - measure does not account for such likelihoods .
therefore , 
 we propose an alternative clustering evaluation measure specifically for this 
 application .
when an som or gsom is 
 used to group species fragments into clusters on a 2d/3d map , it is often 
 inevitable that regions with overlapping clusters ( mixing regions where a 
 neuron represents dna sequence fragments from more than one species ) will 
 exist . to evaluate a clustering algorithm 's ability to group dna sequence 
 fragments into species - specific or 
pure  clusters , we define two criteria that 
 measure the clustering quality in the mixing region : intensity of mix ( iom ) and level of mix ( lom ) , where the former measures the 
 percentage of mixing and the later indicates the taxonomic level of ambiguity 
 for a given pair of clusters . the iom is evaluated based 
 on the concept of mixed pair described below .
let a and b be sets of 
 vectors belonging to species a and b , 
 respectively , and n(x ) is the number of elements in set x. if a and b is a mixed pair , 
 then the percentage of a in the 
 mixing region of the two classes is n(aba)/n(a ) and the percentage of b is n(abb)/n(b ) . as illustrated in figure 1 , 11.6% of a sequences is mixed with b sequences 
 in the b cluster and the 
 complementary mix indicates that 10.6% of b sequences is mixed with a sequences 
 in the a cluster .
the same concept of 
 mixed pair applies for b and c. therefore , there are two mixed pairs 
 in figure 1 , one is a and b and the other is b and c. for k number of species , there can be up to k(k1)/2 mixed 
 pairs .
additionally , a pair of clusters is only considered to be truly mixed when 
 both clusters are heavily overlapped .
thus , as in figure 1 , when n((bcb)/n(b))>threshold  ( th ) but n(bcc)/n(c)<th , it 
 indicates that only a small number of outliers of one species ( c ) is mixed with the other species ( b ) .
we use th = 5% for the threshold of being truly mixed meaning that , statistically , we have a 
 nonmixing confidence of 95% .
the iom measures the amount of mixing sequences and it is nonlinearly categorised into 
 five levels : low ( l ) 5%10% , medium low 
 ( ml ) 10%20% , medium ( m ) 20%40% , medium high ( mh ) 40%60% , and high ( h ) 60%100% .
for example , the iom is ml for the truly mixed pair a and b in figure 1 .
to evaluate clustering results of species , we use lom to describe the taxonomic level of 
 the mixed species .
for example , as in figure 1 , bacillus subtilis is classified in 
 kingdom bacteria and phylum firmicutes .
then the two species are 
 mixed at the phylum level . because of the evolution of organisms , nucleotide 
 composition of genomes belonging to the same lower taxonomic levels can be very 
 similar .
clustering organisms at higher level of taxonomy should be easier than 
 at lower level of taxonomy .
therefore , if truly mixed pair occurs , lower lom ( e.g. , species ) is more acceptable 
 and more desirable than higher lom ( e.g. , 
 kingdom ) . in summary , the 
 proposed two measures are defined as ( 4)iom{l , ml , m , mh , h},lom{species , genus , family , order , class ,  phylum , kingdom}. the two proposed 
 measures , iom and lom , are only defined for truly mixed 
 pairs to evaluate the clustering quality in the mixing regions of a map by the 
 following steps . 

find truly mixed pairs for all pairs of species where if n(xyy)/n(y)th and n(xyx)/n(x)th , then x and y is a truly mixed pair.if x and y are truly mixed , determine iom according to min{n(xyy)/n(y),n(xyx)/n(x)}.identify lom of x and y. 
  find truly mixed pairs for all pairs of species where if n(xyy)/n(y)th and n(xyx)/n(x)th , then x and y is a truly mixed pair .
if x and y are truly mixed , determine iom according to min{n(xyy)/n(y),n(xyx)/n(x)}. identify lom of x and y. clustering results can now be assessed based on three criteria : number 
 of truly mixed pairs , iom , and lom . however , which criterion should have higher priority may vary 
 between applications .
therefore , in our assessment , one result is better than 
 another only when it is superior on at least two of the three measures .
the ncbi database 
 ( http://www.ncbi.nlm.nih.gov ) contains 370 completed microbial genomes in early 2006 , which includes 28 archaea and 342 bacteria . as the investigation 
 seeks to cluster sequences of species ,
one strain was arbitrarily chosen if the same species 
 genome contains more than one strain .
after this process , there were 283 
 genomes remaining . considering the available computing resources and the 
 algorithm comparison focus of this paper ,
two artificial sets of prokaryotic 
 dna sequences ( each of 10 different species out of the 283 species ) were 
 randomly sampled from the ncbi database .
in addition , three simulated metagenomic 
 datasets were created by mavromatis et al .   to facilitate benchmarking of 
 metagenomic data processing methods , which include , but not limited to , binning 
 methods .
the three datasets 
 vary in relative abundance and number of species that represent different complexity levels of real - world microbial 
 communities .
the sequence fragments in the simulated datasets were 
 assembled using three commonly used sequence assembling programs : jazz , arachne , 
 and phrap at u.s .
department of energy ( wash , usa ) , doe joint genome institute 
 ( calif , usa ) . in this paper , we tested one of the three simulated datasets 
 named simmc and was assembled by phrap ( http://www.phrap.com ) . for simplicity , this dataset will be represented as simmc_phrap throughout the paper .
the taxonomic distributions of the three sets of species are 
 displayed graphically in figure 3 .
each 
 letter represents a single species and species within a single rectangle have 
 the same taxonomy at the specific level . 

the names of the species can be found in section 1 of the supplementary material which consists of 
 6 sections showing the species names in 
 section 1 , clustering evaluation methods in sections 2 and 
 3 , and the labelled cluster 
 maps in section 4 to 
 6 
 ( http://www.mame.mu.oz.au/ckkc/binning ) . the numbers below the taxonomic 
 levels in figure 3 indicate the maximum possible 
 number of mixed pairs at that taxonomic level .
for example , in figure 3(a ) , the maximum number of mixed pairs at 
 taxonomic level of class is 12 , which 
 consists a mixed pair each from ( a , j ) and ( c , e ) and 5 pairs each from 
 ( c,{b , d , g , h , i } ) and ( e,{b , d , g , h , i } ) . in the experiments of abe et al .  
that attempts to separate 1  kb and 10  kb dna sequence fragments of 65 
 bacteria genomes containing 54 different species , it is visually shown that 1  kb dna sequence fragments do not carry enough discriminatory information and 
 hence could not completely separate the fragments into species - specific groups . 

therefore , a sequence fragment length of 10  kb is used for the analysis in the 
 two artificial datasets to ensure appropriate separation of species - specific 
 groups .
sequences used in the two artificial datasets are produced from 
 complete genome sequences to simulate the environment of wgs sequencing . such a 
 complete genome sequence is segmented into 10  kb nonoverlapping fragments .
a 
 sliding window with the size n is used 
 for counting the oligonucleotide frequency for each of the fragments in which n is the nucleotide length .
for example , 
 the dinucleotide frequency ( n = 2 ) for 
 a short sequence 
aatacttt  is shown graphically in figure 2 . the oligonucleotide frequency count for each of the fragments yields 
 a single input vector for clustering .
the input vectors to the clustering 
 algorithm will have 4 dimensions . whereas , the 
 simmc_phrap was preprocessed by extracting all sequences with contig length  
 8  kb .
the oligonucleotide frequency count is applied to these sequences to 
 generate the input vectors for clustering .
finally , each input vector is 
 normalised by the sequence length . in order to avoid the algorithm 
 implementation bias ,
an in - house clustering program was developed consisting a 
 data preprocessor , both som and gsom algorithms , and a graphical neuron - map 
 output .
since the hexagonal topology has better 
 topology preservation [ 26 , 29 ] , it is used 
 in both som and gsom .
in addition , the tests were conducted on a pentium 4 3.2  ghz desktop pc running windows xp and the same parameter settings are used in both algorithms for a fair 
 computational speed comparison ( as listed in table 1 ) . to compare results from the 4 orders of oligonucleotide frequencies , 
 we obtain similar map resolution ( number of nodes ) for both algorithms and for 
 all nucleotide frequencies .
since the gsom algorithm automatically determines 
 the number of nodes , it can be used to determine the total number of nodes of 
 som .
this can be achieved by training gsom with a specified resolution ( we used 
 sf = 0.4 ) for the dinucleotide frequency then the final number of nodes in gsom 
 is used to set the number of nodes in som , as well as determine the sf for 
 other nucleotide frequencies .
using this scheme , we set sf = 0.4 for dinucleotide 
 frequency ( for a higher - resolution map ) and experimentally determined that 
 sf = 0.6 for trinucleotide frequency , sf = 0.8 for tetranucleotide frequency and 
 sf = 0.9 for pentanucleotide frequency will result in similar map resolution .
the 
 som also requires setting the aspect ratio of the map and initializing the 
 weight vectors .
the proposed binning 
 method is tested on two artificial datasets and a simulated metagenomic dataset 
 ( simmc_phrap ) which was created and published for benchmarking the metagenomic 
 data processing methods .
the two artificial datasets of prokaryotic dna 
 sequences ( each of 10 different species out of the 283 species ) were randomly sampled 
 from the ncbi database .
each set of the genome sequences was preprocessed to 
 obtain the 4 orders of oligonucleotide frequencies ( di- , tri- , tetra- , and 
 pentanucleotide frequencies ) to form 4 datasets .
this data preprocessing 
 involves segmenting each genome sequence in the set into 10  kb lengths then 
 produce input vectors by calculating the specific oligonucleotide frequency .
after preprocessing , each of the 4 datasets from species set 1 
 contains 4,145 input vectors . whereas , each of the 4 datasets from set 2 
 contains 2,398 input vectors .
the simmc_phrap was preprocessed by extracting all 
 sequences with contig length  8  kb then obtaining the 4 orders of 
 oligonucleotide frequencies to form 4 datasets .
the details of preparing these three datasets can 
 be found in section 2 . to evaluate the 
 clustering performance
a summary 
 of f - measure calculation can be found in section 2 of the supplementary 
 material . from these results
, we 
 can observe that f - measure does not distinguish the clustering quality clearly 
 enough for this species separation application .
for example , in the results of 
 set 1 using gsom , f - measure equals 0.97 for the tri- , tetra- , and 
 pentanucleotide frequencies .
however , by using the proposed evaluation , more 
 details of the ambiguities can be seen .
it shows that there are only two mixed 
 pairs with low taxonomic level in the mixing region when using the 
 pentanucleotide frequency .
however , there are four mixed pairs with two of them 
 having higher taxonomic levels when using the tri- and tetranucleotide 
 frequencies ( as shown in table 3 ) . 

this suggests that the pentanucleotide frequency provides 
 a higher level of phylogenetic resolution , which can not be detected 
 via f - measure because the numbers of incorrectly assigned sequence 
 fragments are similar for these three nucleotide frequencies . 
 
we use two approaches 
 to evaluate the performance of clustering dna sequence fragments of species . 

the first approach is to observe the cluster formation of species sequences to 
 verify the cluster formation similar to the method used by abe et al . .
the second approach is to compare the lom and iom in the mixing 
 region .
after the training is completed , for 
 display purpose , we use the label information of the input data to display the 
 labelled cluster map .
the labelled cluster maps from the training of som and 
 gsom for the pentanucleotide frequency of species set 1 are shown in figure 5 .
all 
 species are clearly clustered and are marked in the figures.the 
 nodes that contain more than 2 species ( which are coloured in grey ) are mostly 
 located at the border of the clusters.species 
  d  is clustered as one group in gsom , but separated by species 
c  into two 
 groups in som.these observations show 
 that the gsom have better cluster formation in terms of cluster identification 
 than the som due to the flexibility of feature map shape .
the labelled cluster 
 maps for other datasets also show a clear cluster formation and can be found in 
 sections 4 , 5 , and 6 of the supplementary material .
the 
 nodes that contain more than 2 species ( which are coloured in grey ) are mostly 
 located at the border of the clusters .
species 
  d  is clustered as one group in gsom , but separated by species 
we also interpret the 
 clustering results of the species mixing regions by summarising the iom and lom in tables 3 , 4 , and 5 for 
 set 1 , set 2 , and simmc_phrap , respectively . by comparing the 
 results of the four orders of oligonucleotide frequencies for set 1 , the number 
 of truly mixed pairs for dataset that uses the dinucleotide frequency is almost 
 twice the number of truly mixed pairs of the higher - order oligonucleotide 
 frequencies as shown in table 3 . in 
 addition , the lom is also high for 
 the dinucleotide frequency . similarly in table 4 , there are three to four truly 
 mixed pairs when using the dinucleotide frequency , but no more than one truly mixed pair when higher - order oligonucleotide 
 frequencies are used .
all four truly mixed pairs are of a very high lom at the phylum level .
since there are 
 only very few species and number of sequence fragments in simmc_phrap , the 
 difference of using different nucleotide frequencies is not obvious .
nevertheless , 
 the results of our two artificial sets indicate that dinucleotide frequency is 
 not a strong signature for clustering the 10  kb fragments of species .
furthermore , from set 
 1 , we can see that iom and lom tend to decrease as the order of oligonucleotide 
 frequency increases .
one would naturally suspect that higher - order 
 oligonucleotide frequencies may carry more information so they can be used to achieve 
 better clustering results .
however , it is not the case for set 2 and 
 simmc_phrap . in set 2
, there is a truly mixed pair in the tetranucleotide 
 frequency but no mixed pair in the tri- and pentanucleotide frequencies when 
 using som . for the gsom algorithm
, a truly mixed pair appears in the 
 pentanucleotide frequency but not in the tri- and tetranucleotide frequencies . 

a detailed examination shows that they are the same pair , acinetobacter sp.adp1 
 and bacillus subtilis subsp .
both 
 of the iom is low indicating a much 
 better result than the dinucleotide frequency . as in table 5 for simmc_phrap
, gsom performs well for all 
 four orders of nucleotide frequencies , whereas som shows inconsistent 
 clustering quality for different nucleotide frequencies .
there are two mixed 
 pairs in the di- and pentanucleotide frequencies but only one mixed pair in the 
 other two nucleotide frequencies .
the mixed pair in the tetranucleotide 
 frequency has the lowest iom ( iom = m ) . 

these results also do not support the hypothesis that 
 higher - order oligonucleotide frequencies are better clustering 
 features .
therefore , we can only 
 conclude that higher - order oligonucleotide frequencies are better features for 
 clustering the species than using dinucleotide frequency . however , the optimal 
 oligonucleotide frequency may vary in different species . in terms of clustering 
 quality , both som and gsom
have similar results . however , besides the mixing 
 quality comparison , we also compare the training speed of them .
the speed comparisons 
 for the first two training phases and the overall training time of both 
 algorithms for all 12 datasets are shown in tables 6 and 7 , respectively . comparing the time 
 taken for som and gsom to finish the first two training phases ( as in table 6 )
this speed improvement can be explained by considering the initial 
 formation of the map structure . as discussed in section 2 ,
however , it increases the computational cost exponentially when 
 the data dimension and size increases .
therefore , even though time consumed for 
 pca initialisation in this experiment is negligible , it is expected to be 
 significant in large - scale metagenomic analysis . in addition , som starts with 
 all nodes fully covering the whole input space then adjusts the weights of all 
 nodes to represent the input data better . on the other hand ,
gsom starts with 
 the minimum number of nodes and grows more nodes in the required direction to 
 get an abstract representation of the input data while still correcting the weights 
 of existing nodes . at the end of the second phase , both algorithms will be 
 roughly representing the abstraction of the data . however , gsom saves time by 
 avoiding pca calculation and operates on fewer numbers of nodes in the first 
 two phases .
although the last training phase is basically identical for both 
 algorithms and the learning length of the last training phase is much longer 
 than the first two phases , gsom still has 7%15% of speed improvement for the 
 overall training .
it was reported that the use of this strategy involving som 
 was used for analysing a large amount of eukaryote genomes and one of the 
 highest performance supercomputers in the world was required . for the large - scale analysis , which can take weeks to complete , 7%15% 
 of speed improvement means 1 - 2 days of time saving for a two - week computation .
besides using tables 6 and 
 7 to compare the training speed of som and gsom , the tables also show that 
 the training time grows exponentially from one order of oligonucleotide 
 frequency to the higher - order oligonucleotide frequency .
it is because of the 
 rapid increment of dimensions when the order of oligonucleotide frequency 
 increases .
we have investigated 
 four orders of oligonucleotide frequencies : di- , tri- , tetra- , and 
 pentanucleotide frequencies on two artificial sets of species and a published 
 simulated metagenomic dataset .
each of the two artificial sets contains 10 
 randomly selected species from ncbi database .
we noticed that the f - measure can 
 not distinguish the clustering quality for this application .
therefore , two 
 methods have been defined for evaluating the performance of clustering dna 
 sequence fragments of species .
this is done by observing the cluster formation 
 with the labelled cluster map and then qualitatively and quantitatively 
 comparing the lom and iom in the mixing region .
the results have shown 
 that dinucleotide frequency is not a sufficiently strong signature for the 
 tested 10  kb dna sequences on the som - based algorithm .
similar to other 
 reports , we also found that higher - order oligonucleotide frequencies , such as 
 tri- , tetra- , and pentanucleotide frequencies , are carrying reasonably adequate 
 genomic information to group intraspecies sequences and separate interspecies 
 sequences [ 12 , 19 ] ; but the required 
 computational power increases exponentially for each increased order of 
 oligonucleotide frequency .
additionally , we noticed that increase of the order 
 of oligonucleotide frequency may deteriorate the assignment of dna sequence 
 fragments to classes in some cases , which indicates the possible existence of 
 optimal species - specific oligonucleotide frequency .
for example , the 
 trinucleotide frequency has a better discrimination power for acinetobacter sp .
therefore , analysts are recommended to start with 
 trinucleotide frequency in large - scale projects and higher - order oligonucleotide 
 frequencies may not always be better .
we also compare the 
 som and gsom algorithms for clustering the dna sequence fragments of species . 

both som and gsom have shown similar results . however , in term of speed 
 comparison , gsom has more than 37% speed  
 improvement over som in the first two 
 training 
 phases and 7%15% speed improvement in the overall training . 
 therefore , gsom is potentially a better alternative clustering tool . as a 
 result of this study , we would suggest to use gsom and a higher - order 
 oligonucleotide frequency ( at least trinucleotide frequency ) to improve the 
 strategy proposed by abe et al .   for the binning process after wgs sequencing .
the method of 
 combining oligonucleotide frequency and the som - based algorithm has provided a 
 promising way of binning after wgs sequencing .
however , there are limitations 
 with this method . since som - based algorithms are essentially data visualisation 
 techniques , it is difficult to identify the exact cluster boundaries when 
 clusters severely overlap with each other
. the overlapping cluster can often be 
 misinterpreted as a single cluster when no label is available .
therefore , a 
 further development to overcome this cluster - overlapping problem is necessary for 
 such som - based binning method to be fully practical .
additionally , at the 
 current state , due to the high diversity of microbial communities and the 
 nature of wgs sequencing , most of the unassembled sequences are less than 10  kb . 
 in order to maximize the use of this binning strategy , more investigation on 
 the optimal sequence length
on 
 the other hand , the rapidly advancing sequencing technology and techniques that 
 are capable of faster sequencing , higher coverage , and longer contig length are 
 continuously being developed [ 33 , 34 ] .
the length of the 
 unassembled fragment is expected to increase in the near future .
therefore , 
 this binning strategy is useful for the analysis after wgs sequencing . 

alternatively , when one is attempting to identify a specific species in the 
 metagenome , which has already been sequenced , supervised learning methods can 
 be applied . while phylopythia employs svm as its supervised learning 
 classifier
, one can opt for other well - known supervised learning methods that 
 has been used in other various applications [ 35 , 36 ] .
 metagenomic projects using whole - genome shotgun ( wgs ) 
     sequencing produces many unassembled dna sequences and small 
     contigs . 
 the step of clustering these sequences , based on 
     biological and molecular features , is called binning . a 
     reported strategy for binning that combines oligonucleotide 
     frequency and self - organising maps ( som ) shows high potential . 
     
 we improve this strategy by identifying suitable training 
     features , implementing a better clustering algorithm , and 
     defining quantitative measures for assessing results . 
 we 
     investigated the suitability of each of di- , tri- , tetra- , and 
     pentanucleotide frequencies . 
 the results show that 
     dinucleotide frequency is not a sufficiently strong signature 
     for binning 10 kb long dna sequences , compared to the other 
     three . 
 furthermore , we observed that increased order of 
     oligonucleotide frequency may deteriorate the assignment 
     result in some cases , which indicates the possible existence 
     of optimal species - specific oligonucleotide frequency . 
 we 
     replaced som with growing self - organising map ( gsom ) where 
     comparable results are obtained while gaining 
     7%15% 
     speed improvement . 
1. INTRODUCTION
2. METHODS
3. RESULTS
4. DISCUSSION, CONCLUSION, AND FUTURE WORK