mass amounts of high - throughput sequenced dna are being produced as a result of metagenomics projects , and new tools are needed to identify the taxonomic content of these environmental samples . currently , biologists have two main goals : ( 1 ) classify as many organisms as possible , and ( 2 ) assess the genes and functions within the sample . this is especially difficult when the sample contains many uncultivated organisms that have no known reference genome . in addition , the reads obtained from these samples can have short lengths from next - generation technologies , complicating the identification process . such technologies are pivotal in order to sequence as much dna as possible within such a sample in a timely fashion but have a  size typically , researchers classify metagenomic reads , or sequenced dna reads , by scoring their alignment to previously sequenced organisms using blast [ 24 ] . unfortunately , this underrepresentation has severely restricted the development of an automated system that recognizes sequences from taxa without completely sequenced genomes [ 5 , 6 ] . in fact , several researchers believe that sequencing error skews our estimates of the abundance of taxa since errors can cause artificial  divergence  in reads , enough to falsely predict new operational taxonomic units ( otus ) [ 5 , 7 ] . recent papers call for ways to infer which species are truly known or unknown from metagenomics samples due to this unwanted variation [ 5 , 7 ] . huson et al . show that anywhere between 10% and 90% of all reads may fail to produce any hits to known genomes when analyzed with blast , and they develop a last common ancestor ( lca ) algorithm to assign reads to the most confident taxon ( class ) . in , brady and salzberg also state that they investigate  confidence scores for predicting the correctness of the classifier , but they are unable to solve this problem . therefore , a detector is clearly needed for composition - based methods to accept / reject reads based on their known / unknown status . in this paper , we address this detection problem and show that we can use the likelihood scores as confidence scores and can interpolate the scores between different read lengths to obtain a consistent detector of  known  reads . in this paper , we develop a detector for  unknown  novel genome reads for use with composition - based methods that can accept / reject reads from novel taxa anywhere in the taxonomic hierarchy . for example , a species - level confidence detector may reject a read but the genus - level detector may accept it . this would indicate that this is a new species within a known genus . to detect these novel genomes , we show that composition - based methods perform better than homology - based methods on the finer resolution of taxonomic levels . the   nave bayes classifier ( nbc ) and phymmbl offer fast and attractive solutions , because they are based on the dna 's compositional word - frequency occurrence and are able to give a log - likelihood score or similar that can be used to develop such a detector [ 8 , 9 ] . nbc and phymm 's ease of use , speed of training and testing , combined with its log - likelihood output ( or in the case of phymmbl , hybrid scores ) make them attractive , simple , yet elegant designs for large - scale metagenomic classification and comparison . in order to design a detector , we partition the available data into three datasets as shown in figure 1 . the first is the  known  dataset , composed of 635 known completed microbial genomes in genbank   that were available as of february 2008 . then , we use a second dataset consisting of 102  novel  genomes , those strains added to genbank from february 2008 to august 2008 . this second dataset is used to train the   detector to determine whether a read belongs to a known or unknown species / genus . finally , we have a third  test unknowns  dataset composed of 275 genomes , added to genbank from august 2008 to november 2009 . we specifically define the term  unknown  as a read 's taxonomic class does not exist in the training database for the particular taxonomic level / rank being classified . for example , some reads may originate from  unknown  species / genera but still be known at the phyla level . concept for each dataset in figure 1 , and describe their composition in detail in the next section . ultimately , we show that such a detector , in conjunction with composition - based likelihood scores , is able to determine if a read originates from unknown species / genera . in order to accomplish this goal , we start by evaluating the accuracy of nbc , blast , and phymmbl on 102 novel genomes for the species and genus levels ( after being trained on the 635 genome training dataset ) . based on this evaluation , we then design a detector : first by using blast scores followed by using the nbc likelihood scores . we also design a detector for phymmbl using the combination of its phymm - likelihood and blast scores . finally , we compare the performance of the classifier+detectors for the nbc and phymmbl approaches on the test dataset of 275 novel genomes to the blast - based methods : megan , sort - items , and carma . because homology - based methods have never been benchmarked for known / novel detection , we will benchmark these for the first time while also developing and benchmarking composition - based detectors . finally , we demonstrate nbc 's , phymmbl 's , and sort - item 's performance on an experimentally acquired acid mine drainage dataset . the 635 microbes of the  known  dataset , from , belong to 470 distinct species and 260 distinct genera . 404 strains are the sole member of their species - class while 171 strains are the sole member of their genus in the dataset . this shows that some knowledge will be lacking when it comes to species- and genus - class diversity . while 66 species contain more than one strain , 89 genera contain more than one strain . the microbial strains genome lengths range from 160  k(bp ) for   candidatus carsonella to 13  mil(bp ) for sorangium cellulosum . in order to design the detector , another 102 strains were acquired from genbank and labeled  novel  and not represented in the  known  training database . 54 of these 102 novel strains belong to 36 known species while the remaining 48 comprise 46  novel  species ( with respect to the  known  database ) . at the next taxonomic level , 81 of the strains belong to 55  known  genera while the remaining 21 comprise 21  novel  genera . this is a good known / unknown representation for different levels of the detector because all strains are novel ( with respect to the training dataset ) , approximately 1/2 of the strains ' species classification is unknown , and approximately 1/5 of the strains ' genera classification is unknown . 275 strains were acquired in november 2009 from ncbi , which were all new , completely sequenced microbial genomes , since august 2008 . the 275 genomes comprise 156 unique genera , of which 64 are in the  known  database and 92 are not , and 216 unique species , of which 48 are  known  and 168 are not . 172 ( 63% ) of the genomes belong to the 64 known genera , and 96 ( 34% ) of the them belong to the 48 known species . strains belong to a diverse set of genera and species ; the 275  172 = 103 ( 37% )  unknown  strains belong to 92 novel genera , and 175  96 = 179 ( 66% ) of the strains belong to 168 novel species . 5 strains from the test set 's genera overlap with the  unknown genera  in 102 genomes used to train the detector . this means that the detector trained on  unknown  genera that is also represented in 2% of the test set . there is a concern that this overlap may have artificially raised accuracy , but the overlap affects only 2% of the sequences , so we conclude that the artificial increase in performance , if any , is negligible . also , all classifiers have the same training advantage , so it is still a fair comparison . therefore , we do not  overtrain  our detector on many examples of  unknowns  that also occur in the test set . it is possible that when designing a detector with a different dataset , some of the unknowns may exist in the  novel  training data , so this is a realistic dataset . also , there is a good distribution of novel to known strains based on which we would expect 37% of the genomes to be rejected ( i.e. , declared by the detector to be unknown ) at the genus level while 66% to be rejected at the species level . to develop a detector , we compose a roc ( receiver operating characteristic ) curve using the likelihood scores of the composition - based methods on the training dataset . each score is associated with the binary decision of whether the genome exists in the database or not . the best operating point on the training dataset is determined as the threshold that obtains the best combined sensitivity and specificity , defined by the the maximum point of the summed sensitivity and specificity metrics . draw 100 l - length reads from each of the 737 full genomes ( coding and noncoding ) , where l = 500 , 100 , 25  bp . score the l - length reads ( using nbc , phymmbl ) , where the scores can be interpreted as posterior probabilities of the genomes predicted by the classifiers . construct an roc curve using the algorithm 's scores and known / unknown labels . select score threshold corresponding to best operating point for the training data ( to be subsequently used on test data ) . we define the following measures which will be used to compare the methods .  detector sensitivity = tp/(tp + fn ) , where tp is the number of true positives ( reads from  known taxa correctly identified ) and fn is the number of false negatives ( reads from  known detector specificity = tn/(tn + fp ) , where tn is the number of true negatives (  unknown  reads correctly identified as unknown ) , and fp is the number of false positives ( unknown reads labeled as  known  ) number . detector   accuracy = total  correct  decision / total  number  of  reads = ( tp + tn)/(tp + fn + fp + tn ) . classifier accuracy = total  correctly  classified / totalnumber  of  reads , where correctly classified means classified correctly into its taxonomic rank . overall classification accuracy = ( total detected as known that are also correctly classified)+tn / total  number  of  reads , where the first term can be approximated by ( tp + fp)(classifier  accuracy ) . the methods , in addition to nbc , can be accessed via the web . nbc   is available for download and online at   http://nbc.ece.drexel.edu/. phymmbl   is available for download from   http://www.cbcb.umd.edu / software / phymm/.   sort - items   is available for download from http://metagenomics.atc.tcs.com / binning / sort - items/.   megan   is available for download from   http://www-ab.informatik.uni-tuebingen.de/software/megan . to compare several methods for the task of detecting novel genomes , we simulate several scenarios . in the first section , we develop a detector ( blast , nbc , and phymmbl ) that accepts / rejects reads of unknown species and genera based on each method 's score ; species / genus levels are informative levels where we would expect to see larger differences between the various methods . also , we narrow our performance comparisons to these levels since many taxa do not have all levels defined ( e.g. , some taxa have species- , genus- , family- and phyla - level labels but are missing family- , and class - level labels in the genbank taxonomy database ) . we only develop the detector for phymmbl and nbc , since there are other blast - based detectors , such as megan , carma , and sort - items that perform such a detection task . as a measure of comparison between roc curves in all sections , we assess the area - under - the - curve ( auc ) metric , a standard measure for detector performance . we then compare the performance of the nbc and phymmbl detectors on a test set and show that they can improve the detector accuracy of the raw method and outperform blast - based methods . we also show the overall classification performance ( binning each read into their associated bins ) in addition to the unknown class . the poor classifier accuracies on novel genomes leads us to ask how well can classifiers predict  unknown  taxa . in other words , can blast 's bit score or nbc's / phymmbl 's score be used to indicate whether a fragment is truly from a new species , genus , and so forth ? here , we show the utility of blast 's bitscore when accepting / rejecting known / unknown reads . in creating the receiver operating characteristic ( roc ) curve for blast 's bitscore , reads are marked as correct if they are correctly classified . in figure 2 , we show blast 's ability to accept / reject reads from known / unknown strains for strain , species , and genus levels . we see that each of the optimal operating points is near 100% sensitivity for the three taxonomic levels while the specificities are around 20% , 35% , and 60% for strains , species , and genera , respectively . blast 's ability to predict taxonomically known and unknown reads using the bit score / e - value while blast is clearly a good classifier for known organisms within its database , it lacks the ability to reject ( declare  unknown  ) novel genomes with both high sensitivity and specificity . we now investigate the feasibility of phymmbl / nbc 's score to develop a better detector for known and unknown taxa from using very short - read reads . to develop a detector using the nbc likelihood scores , we vary a threshold and mark reads correct if they are in the database ( a looser constraint than being correctly classified ) . the auc for the 500  bp reads are marginally better than the 25  bp reads , and , interestingly , the genus and species levels perform the same . the roc curves are also constructed for phymmbl for species- and genus - level performance and 500  bp and 25  bp reads . as seen in figure 4 , the roc shapes are similar to those of blast 's , but with better specificity . the 25  bp species - level specificity for phymmbl is 46% compared to blast 's 35% , and the genus - level specificity is 65% compared to blast 's 60% . the sensitivity that is sacrificed is only a 1 - 2% decrease from blast 's 99% . while the 500  bp and 25  bp genus - level operating points are the same , the 500  bp read 's auc is better than the 25  bp read 's auc . for the species level , the 500  bp operating point and auc are better than the 25  bp operating point . one of the obstacles to using the best derived roc operating point is that the threshold changes according to the fragment length . this is an important aspect to address since in any given dataset from next - generation sequencing technology , the read lengths are variable ( usually with an average length ) . to overcome this obstacle and adjust the threshold for each read length , we interpolate between different operating thresholds for the three read lengths previously , the best operating threshold point was chosen for the 500  bp , 100  bp , and 25  bp reads for each of the strains , species , and genus classifications . the best operating point is determined as the point that obtained the combined best sensitivity and specificity , which sum closest to 200% ( 100% for specificity / sensitivity , resp . ) . for nbc thresholds for example , using this method on the species level , the nbc log - likelihood best operating thresholds were determined to be 8079 , 1445 , and 185 for 500  bp , 100  bp , and 25  bp , respectively . a linear interpolation between these points yields a good fit ( where the r fit value   is 1  3e6 or 1 when rounded ) . on average for the strain , species , and genus classification , the linear log - likelihood fit is y = 16.6x + 210 , where x is the length of the read and y is the likelihood detector threshold . for phymmbl , we found that the best thresholds for species level were 270.6 , 27.4 , and 18.5 for 500  bp , 100  bp , and 25  bp reads . even though the phymmbl scores are not truly likelihood scores ( since they combines phymm 's likelihood score and blast 's e - value ) , the thresholds follow a trend , and we can develop a heuristic interpolation for them . for example , the species - level fit is modeled by y = 0.001x  0.0074x  17.75 ( where the r fit is again nearly 1 ) . the detectors , developed using the 635 known genomes and the 102 unknown genomes , are used to accept or reject 100 reads from each of the 275 new genomes as  known  or  unknown  , respectively . the new 275 genomes are all  unknown  on the strain level but some have  known  status on higher levels ( as described in the materials and methods section ) . in addition to evaluating the detectors , we also assess the ability of megan and sort - items to accept / reject taxa via their capability to classify a read at the species / genus level . the sensitivity , specificity , and detector accuracy are calculated for all methods and can be seen in table 1 . the detectors ' ability to accept / reject reads from novel species was better than accepting / rejecting reads from novel genera , unlike homology - based lca algorithms that perform better at higher - level taxa . this can be due to the fact that there are more unknown species in the set , and , therefore , if the detector 's specificity is high , it will do better on classes with more  unknowns  . to compare the implementations of nbc+detector and phymmbl+detector against current methods , we downloaded megan version 3.7.2 . also , we downloaded the sort - items that was last updated january 7th , 2010 and used tblastx since it requires a protein - blast search . we also benchmarked against webcarma 1.0 , run on march 8 , 2010 . for webcarma , we infered whether a taxon was in the database or not by checking if that taxon showed up in the results file . webcarma only annotated approximately 10,000 of the 27,500 reads resulting in poor genera / species detection and detection accuracy . the results in table 1 , which summarize the sensitivity , specificity , and detection - accuracy of nbc and phymmbl detectors , indicate that the performance of the phymmbl detector is better than the nbc detector for 500  bp and 100  bp reads whereas nbc detector is better for the 25  bp reads . we conjecture that nbc is overfitting the operating - point thresholds due to the linear - interpolation heuristic , which interpolates the operating threshold between different - sized read lengths , and a more intelligent interpolation may be needed . on the test data , phymmbl 's sensitivities were better than nbc 's , but the specificity rates were not as good as nbc 's . nonetheless , phymmbl+detector worked better for most of the reads and species / genus levels . it can achieve around 80% sensitivity and 90% specificity for the species level and 50+% sensitivity and 90+% specificity for the genus level . we hypothesize that nbc , because of its dependence on fixed nmer size overfits the data compared to phymmbl , and therefore the thresholds derived on the training dataset do not extend to the test set as well . megan uses an lca algorithm to determine if a read should be assigned to a particular taxonomic level , and sort - items uses additional alignment information . we used the default parameters for the megan and sort - items . in order to do a fair comparison , we used the same blast reports that were generated for the 500  bp phymmbl analysis for megan , and we obtained a tblastx report for sort - items . for the 27,500 reads , 4 reads did not get scored by blast and , therefore , were not even assessed by the methods . if the method assigned a read at the genus / species level , we determined that this read  passed its built in detector , regardless of the accuracy of the assignment . in other words , if a read is assigned to the family level , it is considered  unknown  at the species / genus levels . if a read is assigned to the species level ( and , therefore , consequently has most upper - level assignments as well ) but is the wrong species and genus , we declare that megan / sort - items detector labels it as  known  ( passed it ) at the species - level and genus - level but misclassified it . if method did not assign a read or assigned it above the species / genus levels ( e.g. , as its family - label ) , we mark it as  rejected  for the species / genus level detection . we observe from table 1 that megan has worse specificity for both species and genus levels , than either nbc , or phymmbl - based detectors . for the genus level , megan has the best sensitivity out of all the methods , although its specificity remains low . in order to be able to take the classifier accuracy into consideration in addition to the detector , we define an    overall  classification accuracy measure as ( number  of  reads  correctly  classified ) + ( number  of  reads  correctly  rejected)/(total  number  of  reads ) . the ( number of reads correctly classified ) can be calculated as ( # of reads that pass the detector that are correctly classified ) . for the species level , megan 's detection accuracy , shown in table 2 is worse than the other detection methods . consequently , its accuracy as a detector is about the same or lower than phymmbl 's detector . sort - items does not classify below the genus level . as a detector , it has low sensitivity and high specificity , but the sensitivity drastically decreases as the reads get shorter . on the other hand , sort - items has a high positive predictive value for the reads it does pass , and , therefore , it has a high detection accuracy for 500  bp on the genus level , which decreases for shorter reads . unknown  genomes were used in the development of the detector as opposed to the 635 known genomes . for nbc+detector and phymmbl+detector , we hypothesize that their performance lowers for genus - level classification compared to the species level because fewer  unknown we conjecture that as the database grows and more  unknown  examples are available , a detector will be more accurate . finally , in table 2 , we show how the methods ' classification accuracy ( without an unknown class ) can be improved with the detector . in this experiment , the classifier method first scores the reads ; then , the reads are accepted or rejected using the detector . nbc , blast , and phymmbl all perform 2035% accuracy for the species and genus level , when used in their native form without a detector ( we do not benchmark blast+detector , since phymmbl uses blast and performs better than blast ) . however , when the detector is added , the classifiers ' overall accuracy , defined as the number of reads correctly rejected plus the number of reads identified as  known  that were correctly classified divided by the total number of reads , significantly improves for both species level and genus - level classification . to calculate megan and sort - items overall classification accuracy , we scored both algorithms ' output as a true positive if it correctly identified the correct genus or species , and we score the output as a true negative if the method only assigned unknown reads to higher than the genus level ( in other words , it could not resolve the correct species / genus ) . for the species level , megan performed worse than classifiers with detectors , as seen in table 2 . for the genus level , both methods are better than nbc+detector but is still worse than phymmbl+detector . we conclude that the purely blast - based or composition based algorithms are not as good as the hybrid phymmbl + detector for determining novel species / genera . a question arises ; how does the structure of the genomes relate to the novel / known detection . since noncoding regions are much more variable than coding regions , are they more susceptible to errors in the detector methods ? we analyzed the 275-genome test set for the composition - based approaches to get an idea of how these different regions perform . we first ran the 27,500 500  bp reads through metagenemark   to annotate the coding regions . we have shown that metagenemark has almost 90% accuracy for predicting coding regions   for 500  bp fragments . metagenemark did not annotate 766 of the reads , resulting in 2.8% of the 500  bp reads as noncoding . since this is a significant stretch of noncoding dna , we expect to have a small proportion . we then examined the accuracy rates of the detector on the coding / noncoding regions in table 3 . we can see that phymmbl has higher accuracy for coding regions than noncoding regions , and nbc is opposite . we hypothesize that since phymmbl partially uses blast , that it is more likely to predict homologous gene regions correctly than noncoding regions . in fact , 32% of noncoding regions failed in the genus - level detection in phymmbl . nbc , on the other hand , which is fully composition based , is more likely to recognize the unique signatures of the noncoding regions  and its noncoding genus - level detection accuracy is almost as high as phymmbl 's , but its discrimination between known and novel gene regions is not sufficient . while it is important to benchmark methods rigorously on a test set , we can only get a true insight into their usage by examining a real dataset . we , therefore , analyze the soudan acid mine red drainage dataset , which is a sample taken near a borehole of the mine . this is a challenging metagenomics sample because there are 317  k reads , where the average read length in this sample is 100  bp , which some researchers claim are very short reads . in the red soudan mine set , the number of organisms found without the detector was 628/631 , using nbc / phymmbl , respectively , out of the 635 . this is most likely false , since acid mine drainage is known to be of low complexity . we also found the median number of reads per organism is 214/340 while the mean is 506/503 with standard deviation of + / 954/545 . so , while there is high variance for high - abundance organisms , there is an  even spread  of hits across the genome training set , highlighting a higher than expected diversity . while the soudan sludge 's diversity may be higher than that studied by tyson et al . , it is doubtful that it is this high , and this issue highlights the difficulty of analysis on soil and water samples complicated by short reads . therefore , the results in this section should be examined in a critical light , as all of these classifiers performed better for longer reads . the idea is to highlight the advantage of using methods that will  filter out  unknown taxa accurately , so that we can gain an accurate assessment of  known  taxa at particular levels . the raw nbc scores found the four most abundant genomes to be ( 1 )   flavobacterium johnsoniae with 12,816 reads , ( 2 )   trichodesmium erythraeum ims101 with 9641 reads , ( 3 )   sorangium cellulosum ( so ce56 ) with 8747 reads , and ( 4 )   clostridium beijerinckii with 7300 reads , johnsoniae et al . are not usually found in marine environments while   trichodesmium erythraeum ims101 is . while these organisms could come from the soil part of the sludge , it is unlikely that they would survive in such a salty environment . for phymmbl ( shown in table 4 ) , the most abundant four genomes are ( 1 )   gramella forsetii with 4102 reads , ( 2 )   marinobacter aquaeolei with 3885 reads , ( 3 )   flavobacterium johnsoniae with 3480 reads , and ( 4 )   dinoroseobacter shibae with 3402 reads . phymmbl has identified marine microbes in 1 , 2 , and 4 that are indeed more likely to be present in the marine sludge . next , the species / genus detectors are evaluated on the dataset . for nbc , only 141 reads out of 317  k passed the species - level detector , and 179 reads passed the genus - level detector . for phymmbl , 794 reads out of the 317  k reads passed the species - level detector while 1053 reads passed the genus - level detector . the detectors may seem too selective because sensitivities of the detectors are suboptimal , as shown in the results section . although as expected , the sensitivity is much higher for the phymmbl detector because it passes more reads . tables 4 and 5 illustrate the distribution of reads that passed the nbc and phymmbl detectors . for nbc , the top hit is   marinobacter hydrocarbonoclasticus , which can degrade hydrocarbons and is found in pollution  therefore , likely to be present in the sample . the second hit ,   ruegeria is known to metabolize sulfur and could play an important part in the acid drainage of the mine , therefore , it is also quite likely to be present in the sample . dinoroseobacter shibae is known for its ability to perform aerobic anoxygenic photosynthesis , and since the red sample of the acid mine drainage is near the surface , it is also likely to be present . in , authors found a wide range of metabolisms in the sample , and nbc passed organisms that had a diversity of metabolisms . therefore , we show the power of the detector to discriminate reads that are most likely to be in our database , as opposed to not applying the detector , in which case  unknown  strains are simply misclassified . phymmbl finds similar organisms but in a different order and since it has higher sensitivity , it is able to find more species / genus reads that pass the detector . the abundant species that are in the top 10 raw reads but did not pass the detector are   gramella forsetii , flavobacterium johnsoniae ,   polaromonas naphthalenivorans ,   aeromonas salmonicida , and rhizobium leguminosarum . gramella forsetii may be truly present as it is reasonable to find in the sample since it degrades polymeric organic matter , but it is usually found in marine environments , so it is difficult to conclude . flavobacterium johnsoniae and aeromonas salmonicida are fish - born pathogens and could actually be present [ 25 , 26 ] , but this again is hard to conclude . polaromonas naphthalenivorans is likely since it grows on hydrocarbons found in contaminated sediment , so that is a misrejection of the classifier . on the other hand , one hypothesis is that reads that correspond to these bacteria may actually be from closely related but unknown species . another hypothesis is that these reads are from horizontally transferred elements which are responsible for particular metabolisms but actually belong to an unknown species . we also compared against sort - items , since this homology - based method had the best 500  bp classification accuracy for the genus level and was comparable to megan for 100  bp reads . compared to nbc / phymm+detector , the main differences are that it accepts gramella and flavobacterium as a likely genera , although the other detectors reject these . it also finds a likely presence of alkalilimnicola , which is an arsenite oxidizing bacterium and is found commonly in contaminated waters . this intuitively seems likely in the acid mine setting and seems to have an advantage over the other methods . sort - items passes   ruegeria , which is known to be in marine - only settings but could be present due to the saline nature . we can see that the phymmbl / nbc+detector methods are more selective in confidently  passing  reads through the detector than sort - items , and we hypothesize that the composition - based methods , such as nbc and phymmbl , better reject some organisms that are unknown at the genus level . however , it may also be true that the sensitivity of these methods may not be as accurate on a real dataset , as seen with the sort - items discovery of the abundance of   alkalilimnicola . all the methods agree that under 1% of the data originates from previously sequenced genera ! this agrees with the hypothesis that 90+% of species can not be cultured and , therefore , have not been previously sequenced . this is an amazing result and shows us the difficult problems that metagenomics samples pose . we only examine species / genus classifications in this paper , but we hypothesize that more than 1% can be successfully classified into higher taxonomic levels . we emphasize that this discussion is an exercise in analyzing an extremely challenging dataset that has a diversity of organisms and short 100  bp reads . in this paper , we introduce a novel / known organism detector , an automated approach to determine whether a given organism is previously known or novel . we also rigorously benchmarked all relevant algorithms to assess their performances and to distinguish novel from known reads . being able to discriminate between next - generation sequencing reads that originate from known novel organisms will allow biologists to make new organism discoveries , have higher confidence in those reads that come from previously sequenced species , and discern other domain - level contaminants ( such as viral or eukaryotic dna ) in the sample . previously developed homology - based methods can be used for such detection , but , as we have shown , those methods are suboptimal , especially at the species level . overall , the phymmbl detector is the best and obtains 85+% accuracy for accepting / rejecting species reads ( in novel detection ) and 70+% for genus reads . in phymmbl , misclassification of reads that pass the detector causes a 10%/3% drop in overall accuracy for 500  bp reads . for example , for the species - level , the detector accuracy is 86.8% , but it is overall classification accuracy ( correctly classifying the known reads plus labeling the unknowns ) is 78.6% . this detection  classification drop is about 4 - 5% for megan , but megan has worse detector / classification accuracy to begin with . an impressive factor in sort - items , is that it only drops 0.2% when classifying reads that pass the detector , meaning this method is very confident in correctly classifying any read that passes its detector . this makes sort - items overall accuracy one of the best for the genus level at 500  bp . the next step will be to implement such a detector for upper levels on the tree of life . the end product will then be to supply a probabilistic threshold to users , so that reads that have a likelihood score above this threshold can be confidently labeled as  known  whereas those whose score falls under this threshold can be confidently labeled as  novel  . such a detector can give a first pass of all the reads that may belong to the database , and would be useful in determining new species . on the other hand , we can also use this system to determine whether a given taxon is novel at deep branching within the tree of life . once reads are identified to come from novel species , they can then be placed in the phylogenetic tree to determine their position in the tree of life . for example , a read that is on the  threshold of detection  may just be another allele of a gene within the same species . those with very low scores are more likely to be novel , and then they will have to be aligned and placed in a tree with other sequences to determine lineages . but with the vast amount of information coming from metagenomics datasets ( with millions of reads ) , obtaining a  first - pass  set of sequences that is a fraction of the original number can significantly reduce computational time of subsequent phylogenetic analysis . this work develops a detector and demonstrates its application to identify known and unknown genomes for composition - based classification methods , and we demonstrate that our detector with a hybrid method outperforms current homology - based methods . effectively , the detector introduces an  unknown  class and enables classification methods to filter out reads that will not be classified correctly , resulting in improved classification accuracy . in addition to detecting novel genomes , we also propose that the detector can be used to filter out noisy reads that have lowconfidence when scored . we use the previously implemented   nave bayes classifier and phymmbl ( interpolated markov model plus blast ) , which assigns a read to the closest match in the database , to design a detector that can detect reads from previously sequenced organisms . we show that nbc and phymmbl scores can be used to determine if a read is from a novel organism in respect to the training database . the overall classification accuracies of composition - based methods are greatly improved when detectors are added to filter out  unknown  organisms . also , there is only a mild decrease in performance when classifying ultrashort reads as opposed to roche 454 length . we determine that the phymmbl + detector classification performs similarly or better than all the methods . overall , the phymmbl detector obtains 85+% accuracy for accepting / rejecting species reads and 70+% for genus reads and only slightly lower in the overall classification accuracy .
high - throughput sequencing technologies enable metagenome profiling , simultaneous sequencing of multiple microbial species present within an environmental sample . since metagenomic data includes sequence fragments (  reads  ) from organisms that are absent from any database , new algorithms must be developed for the identification and annotation of novel sequence fragments . 
 homology - based techniques have been modified to detect novel species and genera , but , composition - based methods , have not been adapted . 
 we develop a detection technique that can discriminate between  known  and  unknown  taxa , which can be used with composition - based methods , as well as a hybrid method . 
 unlike previous studies , we rigorously evaluate all algorithms for their ability to detect novel taxa . 
 first , we show that the integration of a detector with a composition - based method performs significantly better than homology - based methods for the detection of novel species and genera , with best performance at finer taxonomic resolutions . 
 most importantly , we evaluate all the algorithms by introducing an 
  unknown  class and show that the modified version of phymmbl has similar or better overall classification performance than the other modified algorithms , especially for the species - level and ultrashort reads . 
 finally , we evaluate the performance of several algorithms on a real acid mine drainage dataset .