with the rapid development of next - generation sequencing ( ngs ) technologies , the ability to gain experimental data has far surpassed the capability to proceed with further analysis .
high - throughput ngs machine is capable of sequencing millions to even billions of reads ( short dna fragments ) in parallel from a sample containing many species . within a reasonable cost
, an individual laboratory can generate terabase scales of sequencing data within a day , which also inspires many mining tools to interpret these data . instead of traditional works for studying microbial genome on an individual bacterial strain , ngs technologies as a powerful tool greatly facilitates researchers to study the genomes of multiple microorganisms from environmental samples , while it is known as metagenomics .
several metagenomic projects have successfully offered valuable insights to the diverse microbial communities , such as the soil   and human gut .
an important step in metagenomic analysis is the binning procedure to keep together reads from similar species or taxonomic classes .
the former is taxonomy - dependent and similarity - based where individual reads are taxonomically grouped by aligning them to known genomes in reference databases , and subsequently reads aligned to similar genomes are grouped into bins .
however , in a typical metagenomic scenario , most reads ( up to 99% ) come from genomes of hitherto unknown organisms , which are then nonexistent in current reference databases .
taxonomy - dependent binning methods fail to identify such reads , and generally categorize them as unassigned .
one alternative approach is to align the taxonomic marker genes , for example , reca , rpob , and 16s ribosomal rna ( rrna ) , or particular genomic regions , for example , the internal transcribed spacer ( its ) regions . as for the unsupervised method , it is taxonomy - independent and groups reads from the dataset based on the genomic signatures , such as k - mer distribution , g + c content , and codon usage [ 5 , 9 ] , which can be directly extracted from the nucleotide sequences . according to different signatures or observations , a number of composition - based methods are proposed as the binning tools .
abundancebin   utilizes the k - mer frequency to group reads , while toss   is based on sufficiently long mers and integrates abundancebin into separating reads from species with different abundances .
the series of unsupervised binning tools of metacluster   are developed according to multiple observations , and metacluster 5.0 can compute the number of species shaped by the sequence reads .
however , it often gives inaccurate number of species for the relatively large number of species in the dataset from the performance comparison to the binning tool mcluster . on the other hand ,
a cellular automaton ( ca ) is a discrete computational model studied for the complex systems in mathematics , computer science , economics , biology , and so forth .
it consists of a regular array of cells , with each being a finite state automaton ( fsa ) , while the array can be in a positive number of dimensions .
the state of a cell at time t is a function of the states of its neighboring cells at time t  1 , where the function is a set of transition rules .
one - dimensional ca considers the cells over a one - dimensional array and has been used for solving synchronization problems , prime generation , data clustering , real - time language recognition , and so on . in this work , we propose a new binning approach for ngs reads from metagenomic sequences based on one - dimensional ca by the extension of previous work .
since a one - dimensional ca requires only linear memory space when running , our binning method moderates the tremendous amount of memory usage caused by ngs data .
in addition , we conduct experiments to evaluate the performance and compare it with the proposed tool .
subsequently , we take the simulated dataset to assess the performance in section 3 . finally , section 4 draws our conclusion .
cellular automata are discrete models for dynamic systems , where it was originally introduced as a computational medium for machine self - replication guided by a set of rules .
the classical version of ca is based on the use of a regular array , local variables , and a function working over a neighborhood .
more formally , the regular grid of ca is a set of locally interconnected fsas that is typically placed over a regular d - dimensional lattice  .
take the two - dimensional ca as an example , it consists of a lattice of  = m  n squares called cells , where each is in one of a finite number of states .
the neighborhood of a cell c is a set of topologically neighboring cells around c , and a transition rule  applied to c defines the change of each cell in the neighborhood of c from its current state to a new one . at each iteration
though the number of ca applications to engineering problems is relatively few , ca has been largely involved in the simulations of complex systems .
we introduce herein a mathematical model based on the one - dimensional ca , whose cells are placed over a linear lattice  , to describe the binning procedure for metagenomic sequences .
the number of cells in the discrete lattice  equals the number of data items n in the dataset . at the tth iteration , each cell ci(t ) for i   is the ith cell of  and associates with a specific item in the dataset . for a particular r  { 3,4 ,  ,
r } , applying the transition rule r to the cell , ci updates the neighborhood of ci within the range r , where the parameter r can be calculated from the number of cells n. a greater value of r allows a greater size of cluster .
moreover , the boundary condition of one - dimensional ca can be periodic , fixed , or reflecting among others . here
, we set the periodic manner to simulate a circular boundary ; that is , cn+1 = c1 . in the beginning of t
= 0 , the data item is randomly assigned to a cell in  , and then each cell evolves according to the function of its current state and neighboring cells , which is identified by the transition rule r for r  { 3,4 ,  , r}. the value of r starts from 3 due to the minimum requirement of three neighboring cells .
we say that an iteration is finished if all transition rules are performed on each cell in . there are two common terminated criteria to the whole process : one is the user - defined value for the maximum number of iterations and the other is the convergence of  to a stable state ; that is , ci(t ) = ci(t  1 ) , i = 1,2 ,  , n. we adopt the latter criterion in this work . in other words , our algorithm is terminated when there is no state change between two consecutive iterations . at the tth iteration ,
let xi be the data item at the cell ci of . the transition rule r to the cell ci concentrates on three items of xi , xi+1 and xi+r1 by comparing their distances , which is the relation measurement between two items .
let d(xi , xj ) be the distance between two data items xi and xj .
the rule r applied to ci swaps xi+1 and xi+r1 , provided that d(xi , xi+1 ) > d(xi , xi+r1 ) , illustrated by figure 1 ; otherwise , r leaves the data items on ci+1 and ci+r1 unchanged .
for example , the rule 5 compares the distance d(x1 , x2 ) with d(x1 , x5 ) when applying it on c1 , with d(x1 , x6 ) on c2 and so on .
when 5 is applied on the cell cn3 , it considers the distances d(xn3 , xn2 ) and d(xn3 , x1 ) , due to the periodic boundary condition . to compute d(xi , xj ) , two feature vectors xi and xj are extracted , and then we set d(xi , xj)=xi - xj . determining the features of data
typically , ideal features should be useful in distinguishing homologous patterns from the dataset , immune to noises as well as easy to extract and interpret .
such an elegant selection of features can greatly reduce the workload and simplify the subsequent clustering process . for metagenomic data ,
composition - based binning methods have employed several features to assign reads to different groups , where these features can be directly extracted from the nucleotide sequences including the k - mer frequency , g + c content , and codon usage . in this work , we select the k - mer spectrum of a read as its feature .
previous studies suggest that k = 4 or 5 is the better choice to extract features from metagenomic sequences [ 12 , 19 ] . as a result ,
we take k = 5 to represent each read as a 4-dimensional vector , and , by the transition rules , sequence reads with similar feature vectors are assembled .
when the one - dimensional ca converges after a number of iterations , the reads within the same cluster would be arranged in sequence at the lattice .
the transition rules arrange the data with similar feature vectors in a chain of cells , while a problem emerges from the chain order of data : how to group the consecutive data over  as clusters .
a feasible strategy is to identify the boundary point , which is the data object located in the edge of a cluster and thus may have multiple cluster features .
boundary detection of clusters plays an important role in applications , such as image processing and machine learning , but its study is still in the infancy since the first work . as usual
, it is challenging to accurately recognize boundary points in an efficient way due to the interference of noise and outlier points .
we detect the boundary points according to the partial order over  given by the one - dimensional ca .  
figure 2 is the chainmap diagram of our simulation result , in which only the cell numbers from 300 to 800 in the final stationary state are shown .
this diagram is composed of the distances between two items at consecutive cells , and generally the low distances of consecutive cells imply that the corresponding items should be in the same cluster .
conversely , the cells with sharp variation on distances could be candidates for the cluster boundary .
it seems as if the challenge to detect boundary here can be solved by the basic sequential clustering scheme ( bsas ) , but they are slightly different . first , the data items are arranged in a particular order retrieved from the convergence result of one - dimensional ca ; second , the user - specified parameters , including the threshold of dissimilarity and maximum allowable number of clusters , as in the conventional bsas , are not required .
it looks like there are two different clusters in figure 2 because the distance distribution is not consistent in these cells , which inspires us to develop a straightforward way for detecting cluster boundaries . in the final state of one - dimensional ca
let avgk and sdk be the average and standard deviation , respectively , from the starting item of the cluster k to the item xi at ci .
therefore , a item xi is regarded as a starting point of a new cluster if the following three conditions are satisfied : ( 1 ) d(xi , xi+1 ) < avg ; ( 2 ) d(xi1 , xi ) > max(avg , avgk + sdk ) , where xi1 belongs to the cluster k ; ( 3 ) d(xi1 , xi ) > d(xi , xi+1 ) > d(xi+1 , xi+2 ) .
the first criterion asks that the starting point of a new cluster should have a smaller distance than the average ; the second one requests the distance between two consecutive items of a cluster boundary , that is , one is the end and the other is the start of two distinct clusters , respectively , to be bigger enough ; the final criterion emphasizes the relations among consecutive items near the boundary , which is helpful to filter the noise .
we use the three criteria to determine whether xi is the starting point of a new cluster , and if yes , the item xi1 is also the boundary of the preceding cluster .
the binning approach takes the sequencing reads from metagenomic sequences as the input , and its output is to cluster homogeneous reads together as accurate as possible . at first
, our binning method assigns to each read a cell of the lattice  at random .
then , the one - dimensional ca with the transition rules introduced in section 2.2 is invoked to move reads accordingly .
after a number of iterations , the system converges to a stable state where all reads associated with similar feature vectors are continuously placed on . as long as ca arranges the reads in the chain order by composition - based comparison , the next step is to divide the chain into different slices , that is , clusters .
the boundary detection given in section 2.3 shows three criteria so as to find out the cluster boundaries . in some cases , the second condition of the three criteria for boundary detection is easy to achieve because of the small standard deviation for few items in a new cluster , resulting in excessive noises . therefore , the value 30 is used to be the minimum size of cluster as a rule of thumb . in other words , if xi at the cell ci is the starting item of a cluster , then the item located beyond the ( i + 30)th cell can be the boundary candidate of this cluster . by this way
though there is no generally acknowledged benchmark for binning ngs reads at present , several tools are recently proposed for simulating metagenomics , such as art , nessm , bear , and metasim .
our binning method is based on the one - dimensional ca ( 1d - ca ) to automatically determine the clusters for reads , and to validate it , the dataset as the work in   is generated using metasim .
the synthetic dataset d9 in   consists of three species with the average length of 1,000  bp and the read number of 5,000 as well as the abundance ratio of 1  :  3  :  9 .
in addition , we run each experiment ten times and compare the result with mcluster . 

this is a grayscale image with three colors , namely , white , gray , and black , assigned to three species , respectively : white corresponds to the species of the greatest abundance , gray corresponds to the species of the smallest abundance , and black corresponds to the remained one .
there are 144 iterations in total , and due to the great amount of reads , we quarter the strip of diagram as shown in figure 3 . in the beginning of the leftmost columns of the four subdiagrams ,
all reads are put on the lattice in a random order , leading to the mixed colors . at the 6th iteration ,
the leftmost subdiagram shows two distinct blocks , while the number of blocks becomes four at the end of this subdiagram . from the rightmost subdiagram in figure 3
, we can see that the reads located here are hard to be stable and thus the color distribution is in a state of utter chaos . moreover , the rightmost bars of the four subdiagrams in figure 3 are the clustering result of our binning method , in which it fails to identify the clear black block in the leftmost subdiagram . in addition , we run mcluster on the same dataset and compare its performance with our method .
mcluster is developed as the unsupervised method for binning metagenomic sequences , and it has been shown to be better than several works in the overall performance .
we run mcluster ten times as it is identical to ours and compute the average of these simulated results . to evaluate the experimental results , we consider two performance metrics , precision and fp rate .
assume that there are ns species in the dataset and a binning algorithm identifies k clusters c1 , c2 ,  , ck .
let rij be the number of reads in ci that are from species j , and the cluster ci is identified as species s if argjmax(rij ) = s. the precision can then be defined as follows [ 12 , 13 ] : 
 ( 1)precision=i=1kmaxjriji=1kj=1nsrij . since there is no
 unclassified reads  in our binning method , two metrics sensitivity and f - measure are identical to the precision as in ; thus , it is excluded here . moreover
, the other metric fp rate is to measure the number of reads assigned to incorrect species .
let s be the index set of clusters recognized as species s. as a result , the fp rate of a species s , denoted as fpr(s ) , is defined by 
 ( 2)fprs=icsjrij    j=1,2,  ,s1,s+1,  ,nsicsjrij    j=1,2,  ,ns .
given the species s , fpr(s ) measures the false positive condition to all clusters identified as s by the binning method .  
table 1 summarizes the average performances of the simulated result for mcluster and ours . from this table ,
the 1d - ca precision is significantly lower than the mcluster precision ; even so , 1d - ca has something to recommend it . to evaluate the fp rate
, we denote the species of dataset as i , ii , and iii and sort them in descending order according to their abundance ratios ; that is , the most abundant species corresponds to the symbol i.   table 1 shows that fpr(i ) of 1d - ca is far worse than that of mcluster , implying that 1d - ca is not good at identifying abundant specsies , which is contrary to most works [ 1012 ] .
this may be caused by the insensitivity of 1d - ca to detect the cluster boundaries , and hence many reads are inaccurately recognized to the cluster of species i. however , 1d - ca has the best performance in identifying species of lower abundances as shown in table 1 , which helps in extracting rare species from samples and progressing the assembly work with ease .
recent technologies on high - throughput ngs grow rapidly such that it is easy and cheap to sequence all individuals of a microbial community from environmental samples .
metagenomic analysis parses the vast amount of sequence data to mining valuable insights , where the binning process is a crucial step to group sequence reads from similar species or taxonomic classes . due to the read noises and planet - size data ,
, we propose a new binning method based on the one - dimensional cellular automaton ( 1d - ca ) , where 1d - ca has been used for solving synchronization problems , data clustering , language recognition , and so forth .
since 1d - ca requires only linear space when running , our method moderates the tremendous amount of memory usage resulted from ngs reads .
moreover , experiments on synthetic dataset show that our method is helpful to identify species of lower abundance compared to the proposed tool , which facilitates the recognition of rare species from environmental samples .
 more and more developed and inexpensive next - generation sequencing ( ngs ) technologies allow 
 us to extract vast sequence data from a sample containing multiple species . 
 characterizing 
 the taxonomic diversity for the planet - size data plays an important role in the metagenomic 
 studies , while a crucial step for doing the study is the binning process to group sequence reads 
 from similar species or taxonomic classes . 
 the metagenomic binning remains a challenge work 
 because of not only the various read noises but also the tremendous data volume . in this work 
 , 
 we propose an unsupervised binning method for ngs reads based on the one - dimensional cellular 
 automaton ( 1d - ca ) . 
 our binning method facilities to reduce the memory usage because 1d - ca 
 costs only linear space . 
 experiments on synthetic dataset exhibit that our method is helpful to 
 identify species of lower abundance compared to the proposed tool . 
1. Introduction
2. Binning by One-Dimensional Cellular Automaton
3. Experimental Results
4. Conclusions