BACKGROUND
metagenomics is a powerful approach for studying microbial samples, without the needs of isolating and culturing single organisms.
the discipline offers opportunities to discover the complexity and diversity of microbial communities.
earlier metagenomic projects have provided a good understanding of various microbial environments such as acid mine drainage  <cit> , seawater  <cit> , and human gut  <cit> .
with the development of the next-generation sequencing  techniques, e.g.,  <dig> pyrosequencing, illumina genome analyzer, ab solid  <cit> , current metagenomic projects usually process an unprecedented amount of biological data.
moreover, reads generated by the ngs techniques are often less than  <dig> bp  <cit> .
for instance, current illumina read lengths are from  <dig> to  <dig> bp .
these aspects pose major challenges for computational analysis  <cit> .
one of the crucial tasks in a metagenomic project, referred to as taxonomic assignment problem, is to identify the origin of each sequence in an environmental sample.
this task helps in grouping the sequences into bins and determining how they are related to known taxa.
current taxonomic assignment algorithms are mainly based on the composition and similarity features of genomic sequences.
some algorithms only use composition features, e.g., gc-content , oligonucleotide frequencies , which are extracted from both analyzed and reference sequences.
most of those algorithms are proposed to process long reads , and consequently to be inaccurate in short read classification, though they are really fast.
for example, tacoa can only achieve the sensitivity values from  <dig> % to  <dig> % for reads as short as  <dig> bp at the taxonomic levels of order and genus.
it is clear that the lack of composition information in short reads results in the low classification performance of those methods.
besides, some unsupervised binning methods  use composition features, but they do not assign taxonomic identity for reads.
recent taxonomic assignment methods are commonly based on the similarity information between analyzed sequences and sequences in reference databases, which can be obtained by an alignment tool .
megan  <cit>  is a similarity-based method using the lowest common ancestor  algorithm to find the best common ancestor based on blast bit-scores.
one of the drawbacks of the lca is that ambiguous hits may result in assigning reads to taxonomic levels higher than those of their origin.
megan overcomes the problem by using some thresholds related to the bit-scores to filter out the ambiguous hits.
other blast-based algorithms, sort-items  <cit> , and carma <dig>  <cit> , also attempt to address the drawback by using a reciprocal search step to identify significant hits.
the similarity-based methods are demonstrated to be able to work with short reads.
however, a large percentage of reads cannot be classified because those reads do not match to reference sequences or match with extremely low bit-scores.
besides, those methods are very time-consuming because the task of similarity search requires an enormous amount of time.
utilizing the advantages of the combined usage of composition and similarity features are major motivations for currently available hybrid algorithms.
in order to reduce computational time, but still retaining the accuracy like similarity-only based methods, sphinx  <cit>  firstly classifies reference sequences into clusters, and computes the distance between each query sequence and the centriod of the clusters.
the algorithm then only needs to perform blast search for each query against sequences in a cluster, instead of the whole reference sequences.
metacluster-ta  <cit>  and phymmbl  <cit>  are also known as hybrid algorithms.
phymmbl, an extension of phymm  <cit> , uses blast tool to perform similarity search for all reads to provide reference information supporting for the classification process in phymm.
metacluster-ta, on the other hand, can be classified as a semi-supervised method, is a combination of three available algorithms, idba-ud  <cit>  for assembling reads into virtual contigs, metacluster  <dig>   <cit>  for clustering the contigs as well as unassembled sequences, and megan  <cit>  for labeling clusters.
the two algorithms aim to improve the classification quality, but this could make them suffer from more computational expense than similarity-only based methods.
moreover, due to the usage of megan, metacluster-ta does not combinedly use the similarity information of reads with reference sequences in each cluster in the process of cluster labeling.
in this paper, we present a new taxonomic assignment algorithm which uses a semi-supervised cluster-and-label method for metagenomic reads.
the proposed algorithm, called semeta , aims to improve both the quality and computational efficiency of the classification for short reads which sufficiently overlap each other.
after separating reads into clusters, the proposed method assigns each cluster to the best suitable taxon basing on the similarity between their reads and reference databases.
two main new ideas contributed in this work mainly support to the assignment step of the clusters, utilizing output of the clustering process.
firstly, instead of performing the similarity search of all reads in the clusters against reference databases, the method only needs to do for their subgroup of non-overlapping reads so that it can help in reducing overall run-time significantly.
secondly, the similarity information of reads with reference sequences in each cluster are combinedly used for the cluster assignment to produce better classification quality.
the next section presents the details of the proposed algorithm.
the strength of semeta on both simulated and real metagenomic datasets is demonstrated in the section of experimental results.
the final sections are for discussions and conclusions.
methods
fundamentals of proposed method
semi-supervised learning has been known as an efficient technique in many fields, especially in the fields of labeling a large amount of data.
it is expected that the technique helps more data items to be labeled, and the labeling to be more accurate comparing to supervised algorithms due to the support of unsupervised process.
several semi-supervised classification methods have been proposed in the literature  <cit> .
in this study, we proposed a semi-supervised algorithm which can be classified as a cluster-and-label method  <cit> .
the proposed algorithm is based on an assumption that reads tend to form separated clusters, and reads in the same cluster are more likely to share a same label.
given a list of n metagenomic reads.
by using the above assumption, the first step of the proposed method aims to partition the n reads into k sets c <dig> c <dig> …,ck,k≤n.
in the second step, each cluster ci is labeled based on the similarity search of its reads against reference databases.
one of the ideas applied in this study is that instead of performing the similarity search for all reads in each cluster, our method only does for its representative defined as follows.
each representative k of a cluster ci,1≤i≤k, called a core of ci, is its subset which contains only non-overlapping reads.
this is motivated by an observation that although a core k consists of a small number of reads of ci, it still keeps most of the sequence information of ci.
it thus contains the majority of the similarity information between ci and reference sequences.
the idea is exemplified in fig.
<dig>  given a cluster consisting of  <dig> reads which covers from position x to y in a reference sequence.
choosing a subset of the cluster consisting  <dig> reads from r <dig> to r <dig>  it can be seen that the subset also covers most of positions from x to y in the reference sequence.
an experiment conducted in this work  demonstrates that the usage of cluster cores has an extremely light effect on the classification quality while reducing much computation cost.
besides, it can be realized that the cores of clusters are similar to assembled contigs which are possibly generated from the reads.
the procedure applied in this work helps to avoid an assembly process which is very time-consuming  <cit>  while still keeping classification quality.
fig.
<dig> a subset of non-overlapping reads in a cluster.
a cluster consists of  <dig> reads.
a subset of  <dig> non-overlapping reads from r
<dig> to r
<dig> covers most of positions from x to y in the reference sequence.
those reads are also mapped with reference sequences g
<dig> g
<dig> g
<dig> g
<dig> with high bit-scores
in order to determine whether two reads r,s∈r overlap each other or not, this work uses a same method as described in  <cit>  which is based on the number of shared l-mers between reads.
it is stated as follows.
given m,l∈n , if r, and s share at least ml-mers, the two reads are considered as overlapping reads.
otherwise, they are non-overlapping reads  <cit> .
in the step of cluster labeling, a two-level filtering technique is proposed to reduce insignificant hits of the similarity search output .
the first level filters out the blast hits of low bit-scores for each read by using two basic thresholds min-score and top-percent similar to existing studies  <cit> .
the repeat of short sequences between different organisms may cause for the fact that a read may be mapped against reference sequences of different organisms with all high bit-scores, especially with the case of short reads.
thus, it is difficult to distinguish which hits are reliable by only using the first level filtering.
by taking the advantage of the clustering process, an additional filtering is applied at the cluster level.
because reads in the same cluster are more likely to have the same taxon, we label reads in the same cluster together.
the proposed method only chooses the hits which are mapped by the majority of reads in the core of clusters.
for example, assuming that after performing the similarity search for the core consisting of  <dig> reads  in fig.
<dig>  and applying a filtering at the read level, we have  <dig> lists of hits corresponding to the reads .
h1={g <dig> g <dig> g3}, h2={g <dig> g4}, h3={g <dig> g3}, h4={g <dig> g4}, h5={g2}, in which, g <dig> g <dig> g <dig> g <dig> are the names of genomes .
if we choose a threshold is  <dig> %, it means that the hits mapped by at least  <dig> ×5= <dig> reads in the cluster core will be chosen.
therefore, the hit g <dig> is retained, while the others are discarded.
algorithms
this section describes algorithmic aspects of the proposed method in details.
figure  <dig> presents the process of semeta, including two major steps: clustering and taxonomic assignment.
fig.
<dig> process of semeta.
step  <dig> separates reads into clusters, and builds the cluster cores.
step  <dig> does similarity searching between the cores and reference sequences, then labels each cluster
step 1: clustering
in this step, reads are classified into clusters of closely related organisms using an improvement of bimeta  <cit>  - an efficient clustering algorithm for metagenomic reads.
it is similar to bimeta, the proposed algorithm firstly groups reads based on their overlapping information among them.
a k-means algorithm is used to merge the groups into clusters basing on extracted l-mer frequencies of the groups themselves.
however, there are two differences in semeta compared to bimeta.
firstly, since l-mer frequencies extracted from extremely small groups are usually not reliable due to the lack of composition information, semeta removes them from the phase of group merging to improve the clustering precision.
secondly, while bimeta requires the number of clusters in data from users, semeta is able to detect it automatically by using the evaluation function f from the study in  <cit> .
the evaluation method has been demonstrated to be effective for k-means based algorithms.
building cores of clusters
after reads are separated into k clusters c <dig> …,ck, cores of the clusters are built based on the information of overlapping sequence between reads.
a core k,1≤i≤k, of a cluster ci, which will be a representative of the cluster, is equivalent to an independent set or stable set on graphs.
an independent set defined on a graph is a set of vertices which does not consist any pair of adjacent vertices  <cit> .
in this work, a greedy heuristic algorithm is applied to find a maximal independent set of the cluster.
in practice, datasets may contain reads of extremely low-abundance genomes.
these reads are more likely separated into extremely small groups due to the lack of reads overlapping with them.
as a result, they could be removed from the clustering step.
as an effort to label the reads, the proposed algorithm considers them as clusters and puts them to the taxonomic assignment process.
this means that in this case, ci≡k.
step 2: taxonomic assignment
this step consists of the three following tasks:
task  <dig> - similarity search: all reads in cluster cores generated in step  <dig> are mapped against reference databases by the blast tool.
as denoted above, hj,j∈n, is a list of distinct hits returned by the similarity search for a read rj.
each hit t∈hj has a bit-score denoted by bs.
task  <dig> - labeling clusters: the labeling of each cluster ci,1≤i≤k, is based on the mapping results of the reads in its core k against reference databases, described in algorithm  <dig>  the idea behind the algorithm is as follows.
given a list l={hj,1≤j≤|l|}, consisting |l| lists of hits returned by the similarity search for all reads rj∈k, the algorithm performs a filtering technique at two levels: read level and cluster level.
read level: two parameters min-score smin and top-percent ptop are applied.
the threshold min-score smin is used to discard the hits of extremely low bit-scores.
among the remaining hits of each read, the second threshold top-percent ptop allows to choose the highest bit-score hits of them.
cluster level: this level uses a threshold omax to reduce further unreliable hits.
let u be a set of hits, and u=∪j=1|l|hj.
we define a function f:u→n by f=the number of the occurrences of a hit t in l. by using the function, the algorithm only retains the hits which occur in at least omax percentage of the lists in l. if the value of omax leads to that all list hj∈l,1≤j≤|l|, are empty, it will be decreased by half once.
finally, the lowest common ancestor  algorithm is used to find the lowest common taxon of remaining hits after the filtering.
cluster ci as well as all reads r∈ci will be labeled by the common taxon.
task  <dig> - post processing: this task is to merge clusters which have the same label into the same cluster.
some clusters may not be labeled because their reads do not match with any reference sequences or match with extremely low bit-scores.
those reads and the reads of clusters assigned at the highest level of the taxonomy tree will be considered as unassigned reads.
databases
the protein refseq database , including  <dig>  microbial organisms from the ncbi , is used as a reference database.
in order to validate the proposed method in the aspects of assignment for known and unknown species, different variants of the database are created corresponding to two scenarios:
known species: this scenario simulates the case that reference databases contain sequences of species in queries.
unknown species: in this case, sequences of query species are absent in reference databases.
performance metrics
the proposed method is evaluated with metrics which are commonly used in literature  <cit> .
they can be defined as follows.
let n be the total number of reads, and a be the number of assigned reads.
considering at taxonomic level i, let ei be the number of reads assigned to the correct taxa exactly at this level, and ui be the number of reads assigned to the correct taxa under this level.
two metrics sensitivity and precision  can be calculated by the following formulations .
sensitivitya=ei+uin,  precisiona=ei+uia.
for example, given a read originating from mycoplasma fermentans, when we consider at genus level, an assignment of the read as mycolasma would increase ei, and mycoplasma fermentans, mycoplasma gallisepticum would increase ui.
these values are computed at five taxonomic levels: species, genus, family, order, and class.
because each of the metrics precision and sensitivity itself does not fully reflect the performance of an assignment algorithm, we use an additional metric named f-measure emphasizing comprehensively on the both metrics.
it is defined as in  <cit> .
f−measurea=21precisiona+1sensitivitya.
one of the meaningful goals of metagenomic analysis is to discover the dna sequences belonging to novel organisms whose genomes are not present in reference databases.
this can be measured by calculating the total number of reads assigned to the correct taxa exactly at taxonomic levels supported by the evidence.
the assignment to the correct taxa under the taxonomic levels would be counted as incorrect assignment  <cit> .
this study applies the measurement for the database scenario of unknown species as follows.
sensitivityb=∑i∈tein,  precisionb=∑i∈teia,  in which, t=the lowest levels of the correct taxa supported by the evidence.
for example, given a read from a species not present in a reference database.
assuming that sequences from the same family with the organism are available, but no sequences from the same genus are present in the reference database, ei would be counted exactly at family level.
RESULTS
semeta is compared with two well-known similarity-based algorithms on the refseq database: megan  <cit>  , and sort-items  <cit> .
two common parameter thresholds, namely minimum bit-score, and the top-percent, of the three algorithms are set equally of  <dig> and  <dig> %, respectively.
remaining parameters of the megan and sort-items are set by default.
the max-occur threshold omax of the proposed algorithm is set of  <dig> % for all tests.
in order to perform the similarity search, the blastx tool  is downloaded from the ncbi website.
the tool runs with the fast mode , and other parameters are set to default values.
besides, the algorithms use the ncbi taxonomy versions reported in additional file  <dig>
datasets three simulated datasets , named ds <dig> ds <dig> and ds <dig>  respectively, are generated using bacterial genomes from the ncbi database.
these datasets are created by metasim tool  <cit>  following the illumina error profile with length of  <dig> bp, and  <dig> bp, and an error rate of  <dig> %.
the number of genomes in the datasets are  <dig>   <dig>  and  <dig>  dataset ds <dig> and ds <dig> consists of genomes which are described in  <cit> , respectively.
semeta also is used to analyze two real metagenomes.
the first dataset is the acid mine drainage  dataset  <cit>  which consists of  <dig>  sequences, downloaded from ncbi trace archive.
the second real dataset is the sample mh <dig> containing of human gut metagenomic  data  <cit> .
it consists of  <dig> , <dig> illumina paired-end reads with the length of  <dig> bp.
validation of semeta on simulated datasets
semeta is compared with megan and sort-items on the dataset ds <dig>  ds <dig> and ds <dig> for two scenarios of reference databases: known species and unknown species.
for the first scenario, it can be seen from table  <dig> that semeta returns much better results than megan and sort-items at species level.
while sort-items is unable to detect any organisms at this level, semeta achieves from  <dig>  % to  <dig>  % sensitivitya higher than those of megan, and from  <dig>  % to  <dig>  % precisiona higher those of the method for the three datasets.
at the higher levels from genus to class, semeta and megan outperform sortitems in both aspects of the sensitivitya and the precisiona.
although megan gets higher precisiona values than semeta in the levels for dataset ds <dig> and ds <dig>  the proposed method returns better sensitivitya values than megan for all cases.
s
e
n.a
p
r
e.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
s
e
n.a
p
r
e.a
s
e
n.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
<dig>  %
p
r
e.a
<dig>  %
s
e
n.a
p
r
e.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
s
e
n.a
p
r
e.a
s
e
n.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
<dig>  %
p
r
e.a
<dig>  %
s
e
n.a
p
r
e.a
s
e
n.a
p
r
e.a
s
e
n.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
<dig>  %
p
r
e.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
<dig>  %
n/a = not available.
the bold values indicate the best results among the algorithms in the aspect of s
e
n
s
i
t
i
v
i
t
y
a  or p
r
e
c
i
s
i
o
n
a
fig.
<dig> the f- m
e
a
s
u
r
e
a of megan, sort-items, and semeta on simulated datasets for the scenario of known species.
the left chart is for the dataset d
s <dig>  the middle chart is for dataset d
s <dig>  and the right chart is for the dataset d
s3
table  <dig> the performance of megan, sort-items, and semeta on the simulated datasets at different taxonomic levels - the scenario of unknown species
s
e
n.a
p
r
e.a
s
e
n.a
p
r
e.a
s
e
n.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
p
r
e.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
s
e
n.a
p
r
e.a
<dig>  %
<dig>  %
s
e
n.a
p
r
e.a
s
e
n.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
p
r
e.a
<dig>  %
<dig>  %
s
e
n.a
p
r
e.a
s
e
n.a
p
r
e.a
s
e
n.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
p
r
e.a
<dig>  %
<dig>  %
<dig>  %
<dig>  %
the bold values indicate the best results among the algorithms in the aspect of s
e
n
s
i
t
i
v
i
t
y
a  or p
r
e
c
i
s
i
o
n
a
for the higher levels from family to class, it is different from the scenario of known species, semeta outperforms the remaining algorithms for all cases.
our method achieves higher both precisiona and sensitivitya than those of megan and sort-items for most of the cases .
consequently, the f- measuresa of our algorithm are much higher than those of the other methods for all cases in this scenario .
fig.
<dig> the f- m
e
a
s
u
r
e
a of megan, sort-items, and semeta on simulated dataset for the scenario of unknown species.
the left chart is for the dataset d
s <dig>  the middle chart is for dataset d
s <dig>  and the right chart is for the dataset d
s3
in the aspect of assigning reads to the correct taxa exactly at the lowest levels supported by the evidence , semeta and sort-items get higher sensitivityb and precisionb than those of megan for the three datasets .
in addition, while sort-items achieves higher results than semeta for dataset ds <dig>  the proposed algorithm is better than sort-items for dataset ds <dig> and ds <dig>
fig.
<dig> the s
e
n
s
i
t
i
v
i
t
y
b and p
r
e
c
i
s
i
o
n
b of megan, sort-items, and semeta in the case of assigning reads exactly at the lowest taxonomic levels supported by the evidence on simulated datasets
computational costs
considering the computational efficiency, we compute the runtime of different steps of semeta on dataset ds <dig>  and compare them with those of megan, and sort-items.
this experiments is conducted on virtual machines with a hardware configuration of 4-core processor,  <dig> gb ram, running at  <dig>  ghz.
it can be seen from the table  <dig> that semeta spends running time approximately  <dig>  times less than those of megan and sort-items .
for more details, although semeta has to spend time to perform the clustering step while the two other methods do not, the proposed method requires much less runtime than megan and sort-items at the similarity search and assignment steps.s2
n/a = not available
in addition, the similarity search by blast against the reference database  is very time-consuming, and the majority of computational costs of the three algorithms are used for this task.
for example, it costs approximately  <dig> cpu hours to perform the blast search for all  <dig>  queries of dataset ds <dig> on our system, and the task accounts for  <dig>  % of the total running time of megan on this dataset.
thus, the number of blast search against the reference database can help us to estimate roughly the computational costs of the algorithms.
fig.
<dig> the number of blast queries of megan/sort-items, and semeta for simulated datasets
parameter evaluation
further experiments are conducted for dataset ds <dig> to validate the impact of parameters on the performance of semeta.
it can be seen from additional file 1: figures s <dig> to s <dig> that when parameter min-score mmin, and top-percent pmax are not too high , the classification quality of semeta is relatively stable at considered taxonomic levels.
in the other hand, the various values of parameter max-occur omax do not highly affect the performance of semeta at class level.
however, the proposed algorithm gets high sensitivitya and precisiona at species level or genus level when  <dig> %≤omax≤ <dig> %.
in another aspect, semeta achieves high sensitivityb and precisionb values when 40≤mmin≤ <dig> in the case of assigning reads from unknown species exactly at the lowest taxonomic levels supported by the evidence .
when parameter pmax increases, the trend is that the sensitivityb and precisionb of semeta decrease.
in addition, the increase of parameter omax can increase the sensitivityb, but decrease the precisionb of semeta.
the effect of the usage of cluster cores
in order to validate the effect of usage of cluster cores on the classification quality, we compare semeta with its variant in which all reads in each cluster are used for labeling the cluster, instead of using cluster cores.
additional file 1: figure s <dig>  s <dig> and s <dig> compare the performance of semeta with that of the not using core algorithm on dataset ds <dig>  it can be seen from the figures that the usage of cluster cores does not much reduce the classification quality.
at most of the considered taxonomic levels, semeta gets from  <dig>  % to  <dig>  % lower sensitivitya and precisiona than those of the variant algorithm.
besides, not using core algorithm obviously gets slightly better sensitivityb and precisionb than semeta in the aspect of assigning exactly at taxonomic levels.
however, from the experiment, semeta runs approximately  <dig> times faster than the variant algorithm.
results on real datasets
the amd metagenome
by using a traditional method, a study in  <cit>  has revealed that the amd dataset contains five dominant species: leptospirillum sp.
group iii, leptospirillum sp.
group ii, thermoplasmatales archaeon gpl, ferroplasma sp.
type ii, and ferroplasma acidarmanus.
among of them, ferroplasma sp.
type ii, and leptospirillum sp.
group ii have higher abundances than the remaining species.
semeta is able to assign  <dig>  % of the amd sequences, and returns results  supporting the previous observation.
our algorithm has detected three species of them including: ferroplasma sp.
type ii , thermoplasmatales archaeon gpl , and ferroplasma acidarmanus .
besides, because the refseq database does not contain two species leptospirillum sp.
group iii and leptospirillum sp.
group ii, semeta has detected the existence of genus leptospirillum and some species belonging to the taxon.
they account for  <dig>  % in the dataset.
a small remaining percentage of the dataset belongs to other organisms with  <dig>  %.
besides, the number of required blast queries accounts for approximately  <dig>  % of the number of the amd sequences.
fig.
<dig> results of semeta on the amd dataset
the human gut metagenome
for considering the aspect of the computational efficiency of semeta on a large real metagenome, this study conducts an experiment on a sample from the hgm dataset.
the experiment shows that semeta only performs the similarity search for approximately  <dig> % of the total number of sequences in the dataset.
the list of the most abundant taxa detected by the proposed method is presented in additional file 2: table s <dig> , and additional file 2: table s <dig> .
it can be seen that there are  <dig> out of the  <dig> detected species appearing in the list of common microbial species in human gut presented in the study  <cit> , and  <dig> out of  <dig> detected genus are in the list.
the results demonstrate that semeta could be a potential method to work with large metagegomes.
discussions
it is a fact that binning algorithms get more difficult to classify reads at lower taxonomic levels.
from the experimental results, the proposed method outperforms megan and sort-items at the lowest considered levels .
this is resulted from the reason that after reads are grouped into clusters during the clustering step, the filtering step by using parameter max-occur omax at cluster level helps to reduce ambiguous hits successfully, and thus many clusters are assigned correctly to low levels.
the technique also performs effectively for the scenario of unknown species.
in this case, since all sequences of species present in datasets are removed from reference databases, reads in the datasets are likely to be mapped against reference sequences with low bit-scores, and thus many hits are ambiguous.
the filtering makes semeta successful in selecting reliable hits, and helps it to classify reads better than the other methods.
in the clustering step of the proposed algorithm, an expected case is that the number of clusters detected automatically is equal or higher than the number of species in datasets.
when reads from the same species are separated into different clusters, they are likely to be assigned into the same taxon in the second step of the method.
in the case that reads are separated into a smaller number of clusters than the expected one, some clusters which contain reads from different species may be assigned to taxa of higher taxonomic levels .
the prediction of correct taxa for reads from unknown species exactly at the taxonomic levels supported by the evidence, which helps to discover novel organisms directly, is still a challenge.
in this aspect, the sensitivityb and precisionb of the tested methods in the experiments are lower than  <dig> % for the lowest supported levels.
note that, the results corroborate with the previous experiments  <cit>  in which the number of reads assigned correctly is not high for low taxonomic levels.
thus, this could be a future research direction for our work to improve the classification quality of the proposed algorithm.
CONCLUSIONS
in this paper, we present a semi-supervised method to solve the taxonomic assignment of metagnomic reads.
with the support of an unsupervised learning process and an efficient filtering technique at cluster level, the proposed algorithm is able to achieve high classification quality in different aspects.
in case of classifying short reads which have sufficient mutual coverage, semeta outperforms the two other similarity-based methods.
in addition, the usage of reads in cluster cores instead of clusters helps reducing computational costs significantly.
for the demand of processing a huge amount of sequences from microbial communities, the algorithm can be used as a promising tool to analyze metagenomic sequences.
additional files
additional file  <dig>
this file contains the ncbi taxonomy versions used in the experiments, the experimental results to validate the impact of parameters on the classification performance of semeta, and the effect of the usage of cluster cores on semeta.
additional file  <dig>
this file contains the details of the simulated datasets used in this study, and the experimental results of semeta on a sample of human gut metagenome.
competing interests
the authors declare that they have no competing interests.
authors’ contributions
lvv, tvl, and tvh equally contributed to the idea and equally contributed to the design of the experiments.
lvv developed the application.
all authors read and approved the final manuscript.

 metagenomics is a powerful approach for studying microbial samples, without the needs of isolating and culturing single organisms. the discipline offers opportunities to discover the complexity and diversity of microbial communities. earlier metagenomic projects have provided a good understanding of various microbial environments such as acid mine drainage, seawater, and human gut. with the development of the next-generation sequencing techniques, e.g., pyrosequencing, illumina genome analyzer, ab solid, current metagenomic projects usually process an unprecedented amount of biological data. moreover, reads generated by the ngs techniques are often less than bp. for instance, current illumina read lengths are from to bp. these aspects pose major challenges for computational analysis. one of the crucial tasks in a metagenomic project, referred to as taxonomic assignment problem, is to identify the origin of each sequence in an environmental sample. this task helps in grouping the sequences into bins and determining how they are related to known taxa. current taxonomic assignment algorithms are mainly based on the composition and similarity features of genomic sequences. some algorithms only use composition features, e.g., gc-content, oligonucleotide frequencies, which are extracted from both analyzed and reference sequences. most of those algorithms are proposed to process long reads, and consequently to be inaccurate in short read classification, though they are really fast. for example, tacoa can only achieve the sensitivity values from % to % for reads as short as bp at the taxonomic levels of order and genus. it is clear that the lack of composition information in short reads results in the low classification performance of those methods. besides, some unsupervised binning methods use composition features, but they do not assign taxonomic identity for reads. recent taxonomic assignment methods are commonly based on the similarity information between analyzed sequences and sequences in reference databases, which can be obtained by an alignment tool. megan is a similarity-based method using the lowest common ancestor algorithm to find the best common ancestor based on blast bit-scores. one of the drawbacks of the lca is that ambiguous hits may result in assigning reads to taxonomic levels higher than those of their origin. megan overcomes the problem by using some thresholds related to the bit-scores to filter out the ambiguous hits. other blast-based algorithms, sort-items, and carma, also attempt to address the drawback by using a reciprocal search step to identify significant hits. the similarity-based methods are demonstrated to be able to work with short reads. however, a large percentage of reads cannot be classified because those reads do not match to reference sequences or match with extremely low bit-scores. besides, those methods are very time-consuming because the task of similarity search requires an enormous amount of time. utilizing the advantages of the combined usage of composition and similarity features are major motivations for currently available hybrid algorithms. in order to reduce computational time, but still retaining the accuracy like similarity-only based methods, sphinx firstly classifies reference sequences into clusters, and computes the distance between each query sequence and the centriod of the clusters. the algorithm then only needs to perform blast search for each query against sequences in a cluster, instead of the whole reference sequences. metacluster-ta and phymmbl are also known as hybrid algorithms. phymmbl, an extension of phymm, uses blast tool to perform similarity search for all reads to provide reference information supporting for the classification process in phymm. metacluster-ta, on the other hand, can be classified as a semi-supervised method, is a combination of three available algorithms, idba-ud for assembling reads into virtual contigs, metacluster for clustering the contigs as well as unassembled sequences, and megan for labeling clusters. the two algorithms aim to improve the classification quality, but this could make them suffer from more computational expense than similarity-only based methods. moreover, due to the usage of megan, metacluster-ta does not combinedly use the similarity information of reads with reference sequences in each cluster in the process of cluster labeling. in this paper, we present a new taxonomic assignment algorithm which uses a semi-supervised cluster-and-label method for metagenomic reads. the proposed algorithm, called semeta, aims to improve both the quality and computational efficiency of the classification for short reads which sufficiently overlap each other. after separating reads into clusters, the proposed method assigns each cluster to the best suitable taxon basing on the similarity between their reads and reference databases. two main new ideas contributed in this work mainly support to the assignment step of the clusters, utilizing output of the clustering process. firstly, instead of performing the similarity search of all reads in the clusters against reference databases, the method only needs to do for their subgroup of non-overlapping reads so that it can help in reducing overall run-time significantly. secondly, the similarity information of reads with reference sequences in each cluster are combinedly used for the cluster assignment to produce better classification quality. the next section presents the details of the proposed algorithm. the strength of semeta on both simulated and real metagenomic datasets is demonstrated in the section of experimental results. the final sections are for discussions and conclusions. methods fundamentals of proposed method semi-supervised learning has been known as an efficient technique in many fields, especially in the fields of labeling a large amount of data. it is expected that the technique helps more data items to be labeled, and the labeling to be more accurate comparing to supervised algorithms due to the support of unsupervised process. several semi-supervised classification methods have been proposed in the literature. in this study, we proposed a semi-supervised algorithm which can be classified as a cluster-and-label method. the proposed algorithm is based on an assumption that reads tend to form separated clusters, and reads in the same cluster are more likely to share a same label. given a list of n metagenomic reads. by using the above assumption, the first step of the proposed method aims to partition the n reads into k sets c c …,ck,k≤n. in the second step, each cluster ci is labeled based on the similarity search of its reads against reference databases. one of the ideas applied in this study is that instead of performing the similarity search for all reads in each cluster, our method only does for its representative defined as follows. each representative k of a cluster ci,1≤i≤k, called a core of ci, is its subset which contains only non-overlapping reads. this is motivated by an observation that although a core k consists of a small number of reads of ci, it still keeps most of the sequence information of ci. it thus contains the majority of the similarity information between ci and reference sequences. the idea is exemplified in fig. given a cluster consisting of reads which covers from position x to y in a reference sequence. choosing a subset of the cluster consisting reads from r to r it can be seen that the subset also covers most of positions from x to y in the reference sequence. an experiment conducted in this work demonstrates that the usage of cluster cores has an extremely light effect on the classification quality while reducing much computation cost. besides, it can be realized that the cores of clusters are similar to assembled contigs which are possibly generated from the reads. the procedure applied in this work helps to avoid an assembly process which is very time-consuming while still keeping classification quality. fig. a subset of non-overlapping reads in a cluster. a cluster consists of reads. a subset of non-overlapping reads from r to r covers most of positions from x to y in the reference sequence. those reads are also mapped with reference sequences g g g g with high bit-scores in order to determine whether two reads r,s∈r overlap each other or not, this work uses a same method as described in which is based on the number of shared l-mers between reads. it is stated as follows. given m,l∈n, if r, and s share at least ml-mers, the two reads are considered as overlapping reads. otherwise, they are non-overlapping reads. in the step of cluster labeling, a two-level filtering technique is proposed to reduce insignificant hits of the similarity search output. the first level filters out the blast hits of low bit-scores for each read by using two basic thresholds min-score and top-percent similar to existing studies. the repeat of short sequences between different organisms may cause for the fact that a read may be mapped against reference sequences of different organisms with all high bit-scores, especially with the case of short reads. thus, it is difficult to distinguish which hits are reliable by only using the first level filtering. by taking the advantage of the clustering process, an additional filtering is applied at the cluster level. because reads in the same cluster are more likely to have the same taxon, we label reads in the same cluster together. the proposed method only chooses the hits which are mapped by the majority of reads in the core of clusters. for example, assuming that after performing the similarity search for the core consisting of reads in fig. and applying a filtering at the read level, we have lists of hits corresponding to the reads. h1={g g g3}, h2={g g4}, h3={g g3}, h4={g g4}, h5={g2}, in which, g g g g are the names of genomes. if we choose a threshold is %, it means that the hits mapped by at least ×5= reads in the cluster core will be chosen. therefore, the hit g is retained, while the others are discarded. algorithms this section describes algorithmic aspects of the proposed method in details. figure presents the process of semeta, including two major steps: clustering and taxonomic assignment. fig. process of semeta. step separates reads into clusters, and builds the cluster cores. step does similarity searching between the cores and reference sequences, then labels each cluster step 1: clustering in this step, reads are classified into clusters of closely related organisms using an improvement of bimeta - an efficient clustering algorithm for metagenomic reads. it is similar to bimeta, the proposed algorithm firstly groups reads based on their overlapping information among them. a k-means algorithm is used to merge the groups into clusters basing on extracted l-mer frequencies of the groups themselves. however, there are two differences in semeta compared to bimeta. firstly, since l-mer frequencies extracted from extremely small groups are usually not reliable due to the lack of composition information, semeta removes them from the phase of group merging to improve the clustering precision. secondly, while bimeta requires the number of clusters in data from users, semeta is able to detect it automatically by using the evaluation function f from the study in. the evaluation method has been demonstrated to be effective for k-means based algorithms. building cores of clusters after reads are separated into k clusters c …,ck, cores of the clusters are built based on the information of overlapping sequence between reads. a core k,1≤i≤k, of a cluster ci, which will be a representative of the cluster, is equivalent to an independent set or stable set on graphs. an independent set defined on a graph is a set of vertices which does not consist any pair of adjacent vertices. in this work, a greedy heuristic algorithm is applied to find a maximal independent set of the cluster. in practice, datasets may contain reads of extremely low-abundance genomes. these reads are more likely separated into extremely small groups due to the lack of reads overlapping with them. as a result, they could be removed from the clustering step. as an effort to label the reads, the proposed algorithm considers them as clusters and puts them to the taxonomic assignment process. this means that in this case, ci≡k. step 2: taxonomic assignment this step consists of the three following tasks: task - similarity search: all reads in cluster cores generated in step are mapped against reference databases by the blast tool. as denoted above, hj,j∈n, is a list of distinct hits returned by the similarity search for a read rj. each hit t∈hj has a bit-score denoted by bs. task - labeling clusters: the labeling of each cluster ci,1≤i≤k, is based on the mapping results of the reads in its core k against reference databases, described in algorithm the idea behind the algorithm is as follows. given a list l={hj,1≤j≤|l|}, consisting |l| lists of hits returned by the similarity search for all reads rj∈k, the algorithm performs a filtering technique at two levels: read level and cluster level. read level: two parameters min-score smin and top-percent ptop are applied. the threshold min-score smin is used to discard the hits of extremely low bit-scores. among the remaining hits of each read, the second threshold top-percent ptop allows to choose the highest bit-score hits of them. cluster level: this level uses a threshold omax to reduce further unreliable hits. let u be a set of hits, and u=∪j=1|l|hj. we define a function f:u→n by f=the number of the occurrences of a hit t in l. by using the function, the algorithm only retains the hits which occur in at least omax percentage of the lists in l. if the value of omax leads to that all list hj∈l,1≤j≤|l|, are empty, it will be decreased by half once. finally, the lowest common ancestor algorithm is used to find the lowest common taxon of remaining hits after the filtering. cluster ci as well as all reads r∈ci will be labeled by the common taxon. task - post processing: this task is to merge clusters which have the same label into the same cluster. some clusters may not be labeled because their reads do not match with any reference sequences or match with extremely low bit-scores. those reads and the reads of clusters assigned at the highest level of the taxonomy tree will be considered as unassigned reads. databases the protein refseq database, including microbial organisms from the ncbi, is used as a reference database. in order to validate the proposed method in the aspects of assignment for known and unknown species, different variants of the database are created corresponding to two scenarios: known species: this scenario simulates the case that reference databases contain sequences of species in queries. unknown species: in this case, sequences of query species are absent in reference databases. performance metrics the proposed method is evaluated with metrics which are commonly used in literature. they can be defined as follows. let n be the total number of reads, and a be the number of assigned reads. considering at taxonomic level i, let ei be the number of reads assigned to the correct taxa exactly at this level, and ui be the number of reads assigned to the correct taxa under this level. two metrics sensitivity and precision can be calculated by the following formulations. sensitivitya=ei+uin, precisiona=ei+uia. for example, given a read originating from mycoplasma fermentans, when we consider at genus level, an assignment of the read as mycolasma would increase ei, and mycoplasma fermentans, mycoplasma gallisepticum would increase ui. these values are computed at five taxonomic levels: species, genus, family, order, and class. because each of the metrics precision and sensitivity itself does not fully reflect the performance of an assignment algorithm, we use an additional metric named f-measure emphasizing comprehensively on the both metrics. it is defined as in. f−measurea=21precisiona+1sensitivitya. one of the meaningful goals of metagenomic analysis is to discover the dna sequences belonging to novel organisms whose genomes are not present in reference databases. this can be measured by calculating the total number of reads assigned to the correct taxa exactly at taxonomic levels supported by the evidence. the assignment to the correct taxa under the taxonomic levels would be counted as incorrect assignment. this study applies the measurement for the database scenario of unknown species as follows. sensitivityb=∑i∈tein, precisionb=∑i∈teia, in which, t=the lowest levels of the correct taxa supported by the evidence. for example, given a read from a species not present in a reference database. assuming that sequences from the same family with the organism are available, but no sequences from the same genus are present in the reference database, ei would be counted exactly at family level.  semeta is compared with two well-known similarity-based algorithms on the refseq database: megan, and sort-items. two common parameter thresholds, namely minimum bit-score, and the top-percent, of the three algorithms are set equally of and %, respectively. remaining parameters of the megan and sort-items are set by default. the max-occur threshold omax of the proposed algorithm is set of % for all tests. in order to perform the similarity search, the blastx tool is downloaded from the ncbi website. the tool runs with the fast mode, and other parameters are set to default values. besides, the algorithms use the ncbi taxonomy versions reported in additional file datasets three simulated datasets, named ds ds and ds respectively, are generated using bacterial genomes from the ncbi database. these datasets are created by metasim tool following the illumina error profile with length of bp, and bp, and an error rate of %. the number of genomes in the datasets are and dataset ds and ds consists of genomes which are described in, respectively. semeta also is used to analyze two real metagenomes. the first dataset is the acid mine drainage dataset which consists of sequences, downloaded from ncbi trace archive. the second real dataset is the sample mh containing of human gut metagenomic data. it consists of, illumina paired-end reads with the length of bp. validation of semeta on simulated datasets semeta is compared with megan and sort-items on the dataset ds ds and ds for two scenarios of reference databases: known species and unknown species. for the first scenario, it can be seen from table that semeta returns much better results than megan and sort-items at species level. while sort-items is unable to detect any organisms at this level, semeta achieves from % to % sensitivitya higher than those of megan, and from % to % precisiona higher those of the method for the three datasets. at the higher levels from genus to class, semeta and megan outperform sortitems in both aspects of the sensitivitya and the precisiona. although megan gets higher precisiona values than semeta in the levels for dataset ds and ds the proposed method returns better sensitivitya values than megan for all cases. s e n.a p r e.a % % % % s e n.a p r e.a s e n.a % % % % % p r e.a % s e n.a p r e.a % % % % s e n.a p r e.a s e n.a % % % % % p r e.a % s e n.a p r e.a s e n.a p r e.a s e n.a % % % % % p r e.a % % % % % n/a = not available. the bold values indicate the best results among the algorithms in the aspect of s e n s i t i v i t y a or p r e c i s i o n a fig. the f- m e a s u r e a of megan, sort-items, and semeta on simulated datasets for the scenario of known species. the left chart is for the dataset d s the middle chart is for dataset d s and the right chart is for the dataset d s3 table the performance of megan, sort-items, and semeta on the simulated datasets at different taxonomic levels - the scenario of unknown species s e n.a p r e.a s e n.a p r e.a s e n.a % % % % p r e.a % % % % s e n.a p r e.a % % s e n.a p r e.a s e n.a % % % % p r e.a % % s e n.a p r e.a s e n.a p r e.a s e n.a % % % % p r e.a % % % % the bold values indicate the best results among the algorithms in the aspect of s e n s i t i v i t y a or p r e c i s i o n a for the higher levels from family to class, it is different from the scenario of known species, semeta outperforms the remaining algorithms for all cases. our method achieves higher both precisiona and sensitivitya than those of megan and sort-items for most of the cases. consequently, the f- measuresa of our algorithm are much higher than those of the other methods for all cases in this scenario. fig. the f- m e a s u r e a of megan, sort-items, and semeta on simulated dataset for the scenario of unknown species. the left chart is for the dataset d s the middle chart is for dataset d s and the right chart is for the dataset d s3 in the aspect of assigning reads to the correct taxa exactly at the lowest levels supported by the evidence, semeta and sort-items get higher sensitivityb and precisionb than those of megan for the three datasets. in addition, while sort-items achieves higher results than semeta for dataset ds the proposed algorithm is better than sort-items for dataset ds and ds fig. the s e n s i t i v i t y b and p r e c i s i o n b of megan, sort-items, and semeta in the case of assigning reads exactly at the lowest taxonomic levels supported by the evidence on simulated datasets computational costs considering the computational efficiency, we compute the runtime of different steps of semeta on dataset ds and compare them with those of megan, and sort-items. this experiments is conducted on virtual machines with a hardware configuration of 4-core processor, gb ram, running at ghz. it can be seen from the table that semeta spends running time approximately times less than those of megan and sort-items. for more details, although semeta has to spend time to perform the clustering step while the two other methods do not, the proposed method requires much less runtime than megan and sort-items at the similarity search and assignment steps.s2 n/a = not available in addition, the similarity search by blast against the reference database is very time-consuming, and the majority of computational costs of the three algorithms are used for this task. for example, it costs approximately cpu hours to perform the blast search for all queries of dataset ds on our system, and the task accounts for % of the total running time of megan on this dataset. thus, the number of blast search against the reference database can help us to estimate roughly the computational costs of the algorithms. fig. the number of blast queries of megan/sort-items, and semeta for simulated datasets parameter evaluation further experiments are conducted for dataset ds to validate the impact of parameters on the performance of semeta. it can be seen from additional file 1: figures s to s that when parameter min-score mmin, and top-percent pmax are not too high, the classification quality of semeta is relatively stable at considered taxonomic levels. in the other hand, the various values of parameter max-occur omax do not highly affect the performance of semeta at class level. however, the proposed algorithm gets high sensitivitya and precisiona at species level or genus level when %≤omax≤ %. in another aspect, semeta achieves high sensitivityb and precisionb values when 40≤mmin≤ in the case of assigning reads from unknown species exactly at the lowest taxonomic levels supported by the evidence. when parameter pmax increases, the trend is that the sensitivityb and precisionb of semeta decrease. in addition, the increase of parameter omax can increase the sensitivityb, but decrease the precisionb of semeta. the effect of the usage of cluster cores in order to validate the effect of usage of cluster cores on the classification quality, we compare semeta with its variant in which all reads in each cluster are used for labeling the cluster, instead of using cluster cores. additional file 1: figure s s and s compare the performance of semeta with that of the not using core algorithm on dataset ds it can be seen from the figures that the usage of cluster cores does not much reduce the classification quality. at most of the considered taxonomic levels, semeta gets from % to % lower sensitivitya and precisiona than those of the variant algorithm. besides, not using core algorithm obviously gets slightly better sensitivityb and precisionb than semeta in the aspect of assigning exactly at taxonomic levels. however, from the experiment, semeta runs approximately times faster than the variant algorithm. results on real datasets the amd metagenome by using a traditional method, a study in has revealed that the amd dataset contains five dominant species: leptospirillum sp. group iii, leptospirillum sp. group ii, thermoplasmatales archaeon gpl, ferroplasma sp. type ii, and ferroplasma acidarmanus. among of them, ferroplasma sp. type ii, and leptospirillum sp. group ii have higher abundances than the remaining species. semeta is able to assign % of the amd sequences, and returns results supporting the previous observation. our algorithm has detected three species of them including: ferroplasma sp. type ii, thermoplasmatales archaeon gpl, and ferroplasma acidarmanus. besides, because the refseq database does not contain two species leptospirillum sp. group iii and leptospirillum sp. group ii, semeta has detected the existence of genus leptospirillum and some species belonging to the taxon. they account for % in the dataset. a small remaining percentage of the dataset belongs to other organisms with %. besides, the number of required blast queries accounts for approximately % of the number of the amd sequences. fig. results of semeta on the amd dataset the human gut metagenome for considering the aspect of the computational efficiency of semeta on a large real metagenome, this study conducts an experiment on a sample from the hgm dataset. the experiment shows that semeta only performs the similarity search for approximately % of the total number of sequences in the dataset. the list of the most abundant taxa detected by the proposed method is presented in additional file 2: table s, and additional file 2: table s. it can be seen that there are out of the detected species appearing in the list of common microbial species in human gut presented in the study, and out of detected genus are in the list. the results demonstrate that semeta could be a potential method to work with large metagegomes. discussions it is a fact that binning algorithms get more difficult to classify reads at lower taxonomic levels. from the experimental results, the proposed method outperforms megan and sort-items at the lowest considered levels. this is resulted from the reason that after reads are grouped into clusters during the clustering step, the filtering step by using parameter max-occur omax at cluster level helps to reduce ambiguous hits successfully, and thus many clusters are assigned correctly to low levels. the technique also performs effectively for the scenario of unknown species. in this case, since all sequences of species present in datasets are removed from reference databases, reads in the datasets are likely to be mapped against reference sequences with low bit-scores, and thus many hits are ambiguous. the filtering makes semeta successful in selecting reliable hits, and helps it to classify reads better than the other methods. in the clustering step of the proposed algorithm, an expected case is that the number of clusters detected automatically is equal or higher than the number of species in datasets. when reads from the same species are separated into different clusters, they are likely to be assigned into the same taxon in the second step of the method. in the case that reads are separated into a smaller number of clusters than the expected one, some clusters which contain reads from different species may be assigned to taxa of higher taxonomic levels. the prediction of correct taxa for reads from unknown species exactly at the taxonomic levels supported by the evidence, which helps to discover novel organisms directly, is still a challenge. in this aspect, the sensitivityb and precisionb of the tested methods in the experiments are lower than % for the lowest supported levels. note that, the results corroborate with the previous experiments in which the number of reads assigned correctly is not high for low taxonomic levels. thus, this could be a future research direction for our work to improve the classification quality of the proposed algorithm.  in this paper, we present a semi-supervised method to solve the taxonomic assignment of metagnomic reads. with the support of an unsupervised learning process and an efficient filtering technique at cluster level, the proposed algorithm is able to achieve high classification quality in different aspects. in case of classifying short reads which have sufficient mutual coverage, semeta outperforms the two other similarity-based methods. in addition, the usage of reads in cluster cores instead of clusters helps reducing computational costs significantly. for the demand of processing a huge amount of sequences from microbial communities, the algorithm can be used as a promising tool to analyze metagenomic sequences. additional files additional file this file contains the ncbi taxonomy versions used in the experiments, the experimental results to validate the impact of parameters on the classification performance of semeta, and the effect of the usage of cluster cores on semeta. additional file this file contains the details of the simulated datasets used in this study, and the experimental results of semeta on a sample of human gut metagenome. competing interests the authors declare that they have no competing interests. authors’ contributions lvv, tvl, and tvh equally contributed to the idea and equally contributed to the design of the experiments. lvv developed the application. all authors read and approved the final manuscript. 
besides, the lack of similarity information between reads and reference sequences due to the length of short reads reduces significantly the classification quality. taxonomic assignment is a crucial step in a metagenomic project which aims to identify the origin of sequences in an environmental sample. this paper presents a novel taxonomic assignment algorithm, called semeta, which is based on semi-supervised learning to produce a fast and highly accurate classification of short-length reads with sufficient mutual overlap. metagenomicstaxonomic assignmentsemi-supervised learningdna sequencessimilarity searchissue-copyright-statement© the author 2016 it then labels the clusters with the support of an efficient filtering technique on results of the similarity search between their reads and reference databases. the experimental results demonstrate that semeta outperforms two other similarity-based algorithms on different aspects. however, those algorithms suffer from the computational expense because the task of similarity search is very time-consuming. furthermore, instead of performing the similarity search for all reads in the clusters, semeta only does for reads in their subgroups by utilizing the information of sequence overlapping. by using a semi-supervised method as well as taking the advantages of various features, the proposed algorithm is able not only to achieve high classification quality, but also to reduce much computational cost.
 taxonomic assignment is a crucial step in a metagenomic project which aims to identify the origin of sequences in an environmental sample. among the existing methods, since composition-based algorithms are not sufficient for classifying short reads, recent algorithms use only the feature of similarity, or similarity-based combined features. however, those algorithms suffer from the computational expense because the task of similarity search is very time-consuming. besides, the lack of similarity information between reads and reference sequences due to the length of short reads reduces significantly the classification quality.  this paper presents a novel taxonomic assignment algorithm, called semeta, which is based on semi-supervised learning to produce a fast and highly accurate classification of short-length reads with sufficient mutual overlap. the proposed algorithm firstly separates reads into clusters using their composition feature. it then labels the clusters with the support of an efficient filtering technique on results of the similarity search between their reads and reference databases. furthermore, instead of performing the similarity search for all reads in the clusters, semeta only does for reads in their subgroups by utilizing the information of sequence overlapping. the experimental results demonstrate that semeta outperforms two other similarity-based algorithms on different aspects.  by using a semi-supervised method as well as taking the advantages of various features, the proposed algorithm is able not only to achieve high classification quality, but also to reduce much computational cost. the source codes of the algorithm can be downloaded at http://it.hcmute.edu.vn/bioinfo/metapro/semeta.html electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords metagenomicstaxonomic assignmentsemi-supervised learningdna sequencessimilarity searchissue-copyright-statement© the author 2016 