BACKGROUND
rapid and inexpensive sequencing methods yielding short reads have become common for analyzing mixed-species biological samples  <cit> .
phylogenetic and taxonomic classification of species present may be done by extracting and amplifying fragments of a distinctive gene such as one for ribosomal rna from the sample and comparing the results to reference samples  <cit> .
early methods for identification of metagenomic reads were based on blast  <cit> , but these approaches do not define the best phylogenetic placement .
consequently, rigorous phylogenetic methods under the maximum likelihood  principle have been developed for ascertaining the phylogenetic placement of a sequence read in a given species tree  <cit> .
however, an approach using the minimum evolution  principle is not yet available for classifying metagenomic reads, which is important because, as we show below, it is possible to develop a method that does not require heuristics for classifying reads when using a matrix of pairwise distances.
furthermore, methods employing different optimality principles  can be useful in molecular phylogenetics to assess the robustness of inferences to underlying biases of individual methods.
therefore, we have developed a distance-based approach  under the minimum evolution  principle for classifying metagenomics reads.
we have also implemented an efficient procedure for producing bootstrap statistical support for the assignment of any read to any position in the reference species tree.
in the following, we first describe the new method and then assess the absolute accuracy of the new approach by using computer simulations.
we also compare the performance of phyclass with the most accurate existing maximum likelihood based placement program, epa  <cit> .
epa is based on the raxml package  <cit>  and has been shown to perform as well as or better than other methods for this purpose  <cit> .
we also discuss the usefulness of concordance between phyclass and epa inferences in identifying correct assignments even when the statistical support for the read assignment is low.
RESULTS
details of the algorithm
in the phyclass method, the input consists of a set of partial sequences of a specific gene/genomic segment , a reference tree topology  describing the phylogenetic relationships among some set of n species, and a multiple sequence alignment  of the relevant genes or genomic segments for these n species.
for a given read r, the goal is to find a best-fit placement for r in the tree t. this may be done by minimizing the cost, defined as the sum of branch lengths sb,r of the tree containing read r attached to branch b of t, over all possible placements b. under the me principle, the configuration where sb,r is the smallest is the best placement  <cit> .
in this calculation, we use a matrix d of distances among all n+ <dig> sequences .
for all placements of a read, it is only necessary to recalculate pairwise distances between the given read and the n reference sequences, with the pairwise distances among the reference sequences calculated once at the start of the analysis.
furthermore, the calculation of sb,r for all placements of the same read in a fixed reference tree can be done efficiently, because calculating the change between sb,r and sb’,r where b and b’ are adjacent branches of t, requires only a limited calculation involving local branch lengths  <cit> .
therefore, no approximate heuristics are necessary to efficiently apply the me principle by evaluating all possible topological locations for read r. different distance measures may be used for the me computations.
accuracy of the method using complete sequences
we evaluated the performance of the phyclass approach using simulated datasets containing  <dig> sequences .
the dataset is modelled after observed rrna evolutionary parameters, with evolutionary rate varying extensively among lineages in the model tree  resulting in a tree containing a few long branches and many short ones.
this tree was produced by starting with an ultrametric tree of  <dig> arbitrarily selected taxa and then independently varying each branch’s rate over a uniform distribution from  <dig>  substitutions per billion years  to  <dig>  substitutions/gy .
we used seq-gen to produce sequence data sets from this tree  <cit> .
results described below are based on mean ± one standard deviation of results from ten data sets.
we began by establishing a baseline profile, where we assumed that the original full length sequence was available  along with the true msa as query.
in this way, we established the maximum possible accuracy one could achieve if the metagenomics sequence extraction process produced complete full-length error-free sequences that could be aligned perfectly.
we used each individual sequence in the reference tree of  <dig> sequences as a read  for metagenomic analysis by first removing that sequence from the tree and then evaluating the ability of phyclass to replace it at the correct topological position in the tree of  <dig> remaining taxa.
under these conditions, 66%  of the original perfect sequences could be re-assigned correctly .
while this value of fc may appear low given that the data is ideal, it is not surprising because single genes with limited sequence length are known to yield phylogenetic results with rather limited accuracy  <cit> .
this will particularly be the case for short branches because of the effect of sampling error on the ability to bound the length estimates away from zero, which is often the case when highly conserved sequences are used.
in fact, the proportion of branches correct in inferred me trees obtained using the complete and perfect datasets was similar  to the phyclass results , so the phyclass placement error rate is reasonable.
effect of alignment
as the true alignments and perfect sequences are never available in a real metagenomics context, we next examined the performance when using hmmer for aligning query reads to sequences in the reference msa  <cit> .
for added realism, we inflicted three types of errors to the query sequences: 1% of the bases were mutated to another base, another 1% bases were deleted, and 1% bases were duplicated   <cit> .
the resulting accuracy of  <dig> % was lower than the ideal case  .
it is important to realize that the true estimate of the metagenomics accuracy will generally be higher than the fc we report here , because, in our evaluations species corresponding to our queries were never allowed to appear in the reference tree.
that is, we removed the query sequence from the reference tree and alignment before using phyclass.
otherwise, we expect to be able to correctly assign the query to its source data due to the small evolutionary distance between the query and the correct reference sequences.
this was confirmed by our analyses, where the fc for known sequences  was  <dig> % for the simulated dataset.
therefore, the metagenomics read assignment accuracy will be considerably higher when the proportion of sequences from known species is high.
nevertheless, in order to make the tests as challenging as possible, we introduced read errors as described above, applied hmmer instead of using true alignment information, and conducted analyses after deleting the true target species from the tree in all subsequent analyses reported below.
in this sense, our results are worst-case scenarios.
a similar protocol was used in the study by berger et al.
<cit> .
anatomy of misplacements
in order to better understand the anatomy of misplacements, we analyzed the proximity of the erroneous assignments to correct location by recording the number of intervening nodes separating the correct branch and the branch assigned by phyclass  and the evolutionary distance, in terms of mean number of substitutions per site, spanned by the correct and incorrect placement .
for the correct placements, both of them were  <dig>  we found that 43% of the incorrectly placed reads were assigned to a branch immediately adjacent to the correct branch  and the other 40% were assigned on branches that were just two nodes away .
thus, approximately 94% of these placements were made no more than two nodes from their correct position in the tree.
in ordinary  use, evolutionary distance information can also be useful.
for example, if the unknown read is placed into the tree at a long distance from the nearest reference node, then we know that the item has been placed into a relatively isolated phylogenetic position with respect to the reference samples.
this information, which is readily available as all branch lengths in the tree are automatically computed, may be useful as an indicator of reads from anomalous species.
analysis of partial sequences
the analysis of full length sequences as described above represents an ideal case.
in actual metagenomics samples, however, only partial sequences are recovered that may be as short as  <dig> base pairs.
therefore, we examined the accuracy of phyclass when only partial sequences were available.
in this case, reads of different sequence lengths  were extracted from the full length sequences by randomly sampling contiguous blocks of sites.
for each of the  <dig> species, one sample of each length was extracted, the different kinds of noise were applied, and the resulting simulated query was aligned to the full reference set.
as expected, the shortest reads show the lowest assignment accuracy .
the accuracy trends showed a log-linear relationship with read length.
with a 16-fold decrease in read length , the fraction of correct assignments is halved.
similar trends, but in the inverse direction, were seen for the branch length separation  as well as node separation per incorrect assignment .
distance measures
we hypothesized that an additional factor affecting accuracy is evolutionary distance measure used, although it was not clear a priori what the effect would be, as more sophisticated evolutionary models reduce distance estimation bias, but also increase the variance of the estimate  <cit> .
for the above results, we used p-distance , which has a relatively small estimation variance and is computable for all sequence pairs, unlike more sophisticated distance measures that often fail .
it is known that p-distance is a good approximation to more sophisticated model-based distances over short evolutionary distances, and it is generally these distances we are most concerned with when making difficult differentiations among closely-placed nodes on short branches  <cit> .
use of p-distance in an me context is further supported in several studies which found that, unless sequence lengths are very great, the simple p-distance generally gives better results in phylogenetic inference than more complicated distance measures  <cit> .
in agreement with these results, empirical tests using phyclass on our data sets show that p-distance performed slightly better than more sophisticated distances in terms of placement accuracy.
for shorter sequences, p-distance provided improved accuracy over a very sophisticated distance measure  based on the maximum composite likelihood method  <cit>  with a gamma model to account for rate variation among sites  <cit> , which matched the tamura-nei model  <cit>  used to generate the sequence data according to the tree.
significance of placements
we assess the statistical significance of the placement using the bootstrap resampling procedure, where the n pairwise distances between the given read and the n reference sequences in the msa are obtained by using multinomial sampled counts of  <dig>  possible nucleotide pairs for each read-reference sequence comparison.
therefore, the pairwise distances in d corresponding to the read-reference pairs are updated in bootstrap replicate based on the multinomial counts, with rest of the pairwise distances, ½ n×, between reference sequence pairs remaining the same in every bootstrap replicate, because the topology of the reference tree is assumed to be fixed in each replicate.
we used p-distances, as bootstrapping for these distances is fast to compute using the multinomial sampling.
as expected, higher average bootstrap support was seen for the longer reads .
more importantly, the fraction of correct placements receiving high bootstrap score was much higher than the wrong assignments .
but, still, there were many misclassifications receiving support of at least 50% .
a reason for correct placements without high bootstrap support and incorrect placements with more than 50% bootstrap support was the paucity of substitutions in the section of the reference alignment that overlaps with the query sequence.
this problem of zero or effectively zero branch lengths cannot be remedied by any method, because there is no information in the data for correctly placing queries when they come from such branches  <cit> .
when the correct placement of a query requires insertion into such a branch, attempts at placement only contribute to noise, which obscures efforts to compare results under different conditions.
therefore, the bootstrap support values, and those obtained using other confidence assessment approaches, need to be used carefully when the placement of a read is at or adjacent to a very short branch.
additional data sets
we performed testing using four additional data sets.
three of these were taken from a similar study in the literature  <cit> .
these are based on empirical sequence data sets.
these sets were aligned and a ml tree for them constructed as described in that paper.
in the absence of knowledge of the true phylogeny of the sequences, these trees were taken as truth for the purpose of determining accuracy.
the fourth data set was simulated using the same tree topology as in the primary example but with constant evolutionary rate .
figure  <dig> shows overall percentage correct for all sets by query length.
note that there is considerable variation among the different sets , with the set that we call d <dig> the most difficult to classify.
this may be due to the many indels in the sequences for that set —only  <dig> of the  <dig> sites have complete coverage.
note.- sequence length is the length of the original alignment in nucleotide sites .
ref.
sequences refers to the number of sequences in the alignment.
mean branch length is the average length  of branches in the original tree.
indels is the percentage of sites in the alignment that are hyphens or question marks or iupac n metacharacters, representing any nucleotide.
tree diameter is the maximum patristic evolutionary distance  between any two taxa in the tree.
source refers to the origin of the sequences.
comparison with epa
in order to assess the value of phyclass in the context of the state of the art, we compared its accuracy with epa which is widely used.
epa chooses optimal placement using a heuristic approximation of the total maximum likelihood  of the candidate trees  <cit> .
it is based on the widely-used ml tree inference program raxml  <cit> .
the accuracy of epa was consistently approximately  <dig> error percentage points higher than phyclass over all query lengths for the model s500r data set and a similar amount on the empirical data sets .
this is consistent with slightly better performance of likelihood-based methods over me methods .
speed
although our goal here is to evaluate the accuracy of the phyclass method, and not to do time optimizations, especially if they involve heuristic shortcuts that may lead to sub-optimal placement, we made some observations about timings.
currently, our prototype phyclass classifier, exclusive of one-time initial alignment using hmmer, takes around  <dig> seconds per query to compute one placement on the s500r data set.
this is compared to the performance of epa with the “slow” option  which used around  <dig> seconds per query.
there are several clear opportunities for time optimizations in phyclass without compromising the current strictly optimal me calculation.
in our prototype version of phyclass, each query is processed completely independently and most time is spent in reading and writing text files, setting up data structures and formatting them for output.
this is appropriate, since, because of the test mode requirement of removing the true source taxon from the tree and the reference set to see if it is re-inserted at the same point, the data changes with each query.
most of this can be eliminated in more typical use by running a large number of queries in batch mode so that most computation  can be factored out of the per-query workload into a setup phase and held in computer memory rather than written to external files.
an analysis of the 6-second runtime of phyclass on the s500r data set shows that more than half is consumed reading and writing text files, with the remainder divided between distance and sum-of-branch-length calculations, the former of which can be factored to a set-up phase instead of being done on a per-query basis.
epa already incorporates optimizations to pre-compute and retain in memory as much as possible.
phyclass and epa used together
finally, we explored whether placement can be improved by using both methods discussed above  in conjunction with each other .
we found that, using a mixture of equal numbers of query lengths  based on the s500r data set, phyclass alone correctly classified 40% of queries, and epa correctly classified 41%.
however, for the 32% of the data for which phyclass and epa agreed, correctly or incorrectly, on the placement, 80% is classified correctly.
in this way, we are able to roughly double the accuracy rate for about a third of the queries.
this dual approach may be considered an advantage over traditional bootstrapping, which is usually conservative and time consuming.
CONCLUSIONS
using sequence simulation, we evaluated the use of the minimum evolution principle to place aligned fragmented dna sequences representing metagenomic reads into phylogenetically correct positions in an existing tree of known sequences.
our tests showed the accuracy of the new method to be comparable to, but in most cases slightly less than that of the best existing maximum likelihood program to deal with the same problem.
consensus assignments based on both approaches together were found to be often more correct than either method individually, even when the statistical support for assignments was low.

 rapid and inexpensive sequencing methods yielding short reads have become common for analyzing mixed-species biological samples. phylogenetic and taxonomic classification of species present may be done by extracting and amplifying fragments of a distinctive gene such as one for ribosomal rna from the sample and comparing the results to reference samples. early methods for identification of metagenomic reads were based on blast, but these approaches do not define the best phylogenetic placement. consequently, rigorous phylogenetic methods under the maximum likelihood principle have been developed for ascertaining the phylogenetic placement of a sequence read in a given species tree. however, an approach using the minimum evolution principle is not yet available for classifying metagenomic reads, which is important because, as we show below, it is possible to develop a method that does not require heuristics for classifying reads when using a matrix of pairwise distances. furthermore, methods employing different optimality principles can be useful in molecular phylogenetics to assess the robustness of inferences to underlying biases of individual methods. therefore, we have developed a distance-based approach under the minimum evolution principle for classifying metagenomics reads. we have also implemented an efficient procedure for producing bootstrap statistical support for the assignment of any read to any position in the reference species tree. in the following, we first describe the new method and then assess the absolute accuracy of the new approach by using computer simulations. we also compare the performance of phyclass with the most accurate existing maximum likelihood based placement program, epa. epa is based on the raxml package and has been shown to perform as well as or better than other methods for this purpose. we also discuss the usefulness of concordance between phyclass and epa inferences in identifying correct assignments even when the statistical support for the read assignment is low.  details of the algorithm in the phyclass method, the input consists of a set of partial sequences of a specific gene/genomic segment, a reference tree topology describing the phylogenetic relationships among some set of n species, and a multiple sequence alignment of the relevant genes or genomic segments for these n species. for a given read r, the goal is to find a best-fit placement for r in the tree t. this may be done by minimizing the cost, defined as the sum of branch lengths sb,r of the tree containing read r attached to branch b of t, over all possible placements b. under the me principle, the configuration where sb,r is the smallest is the best placement. in this calculation, we use a matrix d of distances among all n+ sequences. for all placements of a read, it is only necessary to recalculate pairwise distances between the given read and the n reference sequences, with the pairwise distances among the reference sequences calculated once at the start of the analysis. furthermore, the calculation of sb,r for all placements of the same read in a fixed reference tree can be done efficiently, because calculating the change between sb,r and sb’,r where b and b’ are adjacent branches of t, requires only a limited calculation involving local branch lengths. therefore, no approximate heuristics are necessary to efficiently apply the me principle by evaluating all possible topological locations for read r. different distance measures may be used for the me computations. accuracy of the method using complete sequences we evaluated the performance of the phyclass approach using simulated datasets containing sequences. the dataset is modelled after observed rrna evolutionary parameters, with evolutionary rate varying extensively among lineages in the model tree resulting in a tree containing a few long branches and many short ones. this tree was produced by starting with an ultrametric tree of arbitrarily selected taxa and then independently varying each branch’s rate over a uniform distribution from substitutions per billion years to substitutions/gy. we used seq-gen to produce sequence data sets from this tree. results described below are based on mean ± one standard deviation of results from ten data sets. we began by establishing a baseline profile, where we assumed that the original full length sequence was available along with the true msa as query. in this way, we established the maximum possible accuracy one could achieve if the metagenomics sequence extraction process produced complete full-length error-free sequences that could be aligned perfectly. we used each individual sequence in the reference tree of sequences as a read for metagenomic analysis by first removing that sequence from the tree and then evaluating the ability of phyclass to replace it at the correct topological position in the tree of remaining taxa. under these conditions, 66% of the original perfect sequences could be re-assigned correctly. while this value of fc may appear low given that the data is ideal, it is not surprising because single genes with limited sequence length are known to yield phylogenetic results with rather limited accuracy. this will particularly be the case for short branches because of the effect of sampling error on the ability to bound the length estimates away from zero, which is often the case when highly conserved sequences are used. in fact, the proportion of branches correct in inferred me trees obtained using the complete and perfect datasets was similar to the phyclass results, so the phyclass placement error rate is reasonable. effect of alignment as the true alignments and perfect sequences are never available in a real metagenomics context, we next examined the performance when using hmmer for aligning query reads to sequences in the reference msa. for added realism, we inflicted three types of errors to the query sequences: 1% of the bases were mutated to another base, another 1% bases were deleted, and 1% bases were duplicated. the resulting accuracy of % was lower than the ideal case. it is important to realize that the true estimate of the metagenomics accuracy will generally be higher than the fc we report here, because, in our evaluations species corresponding to our queries were never allowed to appear in the reference tree. that is, we removed the query sequence from the reference tree and alignment before using phyclass. otherwise, we expect to be able to correctly assign the query to its source data due to the small evolutionary distance between the query and the correct reference sequences. this was confirmed by our analyses, where the fc for known sequences was % for the simulated dataset. therefore, the metagenomics read assignment accuracy will be considerably higher when the proportion of sequences from known species is high. nevertheless, in order to make the tests as challenging as possible, we introduced read errors as described above, applied hmmer instead of using true alignment information, and conducted analyses after deleting the true target species from the tree in all subsequent analyses reported below. in this sense, our results are worst-case scenarios. a similar protocol was used in the study by berger et al.. anatomy of misplacements in order to better understand the anatomy of misplacements, we analyzed the proximity of the erroneous assignments to correct location by recording the number of intervening nodes separating the correct branch and the branch assigned by phyclass and the evolutionary distance, in terms of mean number of substitutions per site, spanned by the correct and incorrect placement. for the correct placements, both of them were we found that 43% of the incorrectly placed reads were assigned to a branch immediately adjacent to the correct branch and the other 40% were assigned on branches that were just two nodes away. thus, approximately 94% of these placements were made no more than two nodes from their correct position in the tree. in ordinary use, evolutionary distance information can also be useful. for example, if the unknown read is placed into the tree at a long distance from the nearest reference node, then we know that the item has been placed into a relatively isolated phylogenetic position with respect to the reference samples. this information, which is readily available as all branch lengths in the tree are automatically computed, may be useful as an indicator of reads from anomalous species. analysis of partial sequences the analysis of full length sequences as described above represents an ideal case. in actual metagenomics samples, however, only partial sequences are recovered that may be as short as base pairs. therefore, we examined the accuracy of phyclass when only partial sequences were available. in this case, reads of different sequence lengths were extracted from the full length sequences by randomly sampling contiguous blocks of sites. for each of the species, one sample of each length was extracted, the different kinds of noise were applied, and the resulting simulated query was aligned to the full reference set. as expected, the shortest reads show the lowest assignment accuracy. the accuracy trends showed a log-linear relationship with read length. with a 16-fold decrease in read length, the fraction of correct assignments is halved. similar trends, but in the inverse direction, were seen for the branch length separation as well as node separation per incorrect assignment. distance measures we hypothesized that an additional factor affecting accuracy is evolutionary distance measure used, although it was not clear a priori what the effect would be, as more sophisticated evolutionary models reduce distance estimation bias, but also increase the variance of the estimate. for the above results, we used p-distance, which has a relatively small estimation variance and is computable for all sequence pairs, unlike more sophisticated distance measures that often fail. it is known that p-distance is a good approximation to more sophisticated model-based distances over short evolutionary distances, and it is generally these distances we are most concerned with when making difficult differentiations among closely-placed nodes on short branches. use of p-distance in an me context is further supported in several studies which found that, unless sequence lengths are very great, the simple p-distance generally gives better results in phylogenetic inference than more complicated distance measures. in agreement with these results, empirical tests using phyclass on our data sets show that p-distance performed slightly better than more sophisticated distances in terms of placement accuracy. for shorter sequences, p-distance provided improved accuracy over a very sophisticated distance measure based on the maximum composite likelihood method with a gamma model to account for rate variation among sites, which matched the tamura-nei model used to generate the sequence data according to the tree. significance of placements we assess the statistical significance of the placement using the bootstrap resampling procedure, where the n pairwise distances between the given read and the n reference sequences in the msa are obtained by using multinomial sampled counts of possible nucleotide pairs for each read-reference sequence comparison. therefore, the pairwise distances in d corresponding to the read-reference pairs are updated in bootstrap replicate based on the multinomial counts, with rest of the pairwise distances, ½ n×, between reference sequence pairs remaining the same in every bootstrap replicate, because the topology of the reference tree is assumed to be fixed in each replicate. we used p-distances, as bootstrapping for these distances is fast to compute using the multinomial sampling. as expected, higher average bootstrap support was seen for the longer reads. more importantly, the fraction of correct placements receiving high bootstrap score was much higher than the wrong assignments. but, still, there were many misclassifications receiving support of at least 50%. a reason for correct placements without high bootstrap support and incorrect placements with more than 50% bootstrap support was the paucity of substitutions in the section of the reference alignment that overlaps with the query sequence. this problem of zero or effectively zero branch lengths cannot be remedied by any method, because there is no information in the data for correctly placing queries when they come from such branches. when the correct placement of a query requires insertion into such a branch, attempts at placement only contribute to noise, which obscures efforts to compare results under different conditions. therefore, the bootstrap support values, and those obtained using other confidence assessment approaches, need to be used carefully when the placement of a read is at or adjacent to a very short branch. additional data sets we performed testing using four additional data sets. three of these were taken from a similar study in the literature. these are based on empirical sequence data sets. these sets were aligned and a ml tree for them constructed as described in that paper. in the absence of knowledge of the true phylogeny of the sequences, these trees were taken as truth for the purpose of determining accuracy. the fourth data set was simulated using the same tree topology as in the primary example but with constant evolutionary rate. figure shows overall percentage correct for all sets by query length. note that there is considerable variation among the different sets, with the set that we call d the most difficult to classify. this may be due to the many indels in the sequences for that set —only of the sites have complete coverage. note.- sequence length is the length of the original alignment in nucleotide sites. ref. sequences refers to the number of sequences in the alignment. mean branch length is the average length of branches in the original tree. indels is the percentage of sites in the alignment that are hyphens or question marks or iupac n metacharacters, representing any nucleotide. tree diameter is the maximum patristic evolutionary distance between any two taxa in the tree. source refers to the origin of the sequences. comparison with epa in order to assess the value of phyclass in the context of the state of the art, we compared its accuracy with epa which is widely used. epa chooses optimal placement using a heuristic approximation of the total maximum likelihood of the candidate trees. it is based on the widely-used ml tree inference program raxml. the accuracy of epa was consistently approximately error percentage points higher than phyclass over all query lengths for the model s500r data set and a similar amount on the empirical data sets. this is consistent with slightly better performance of likelihood-based methods over me methods. speed although our goal here is to evaluate the accuracy of the phyclass method, and not to do time optimizations, especially if they involve heuristic shortcuts that may lead to sub-optimal placement, we made some observations about timings. currently, our prototype phyclass classifier, exclusive of one-time initial alignment using hmmer, takes around seconds per query to compute one placement on the s500r data set. this is compared to the performance of epa with the “slow” option which used around seconds per query. there are several clear opportunities for time optimizations in phyclass without compromising the current strictly optimal me calculation. in our prototype version of phyclass, each query is processed completely independently and most time is spent in reading and writing text files, setting up data structures and formatting them for output. this is appropriate, since, because of the test mode requirement of removing the true source taxon from the tree and the reference set to see if it is re-inserted at the same point, the data changes with each query. most of this can be eliminated in more typical use by running a large number of queries in batch mode so that most computation can be factored out of the per-query workload into a setup phase and held in computer memory rather than written to external files. an analysis of the 6-second runtime of phyclass on the s500r data set shows that more than half is consumed reading and writing text files, with the remainder divided between distance and sum-of-branch-length calculations, the former of which can be factored to a set-up phase instead of being done on a per-query basis. epa already incorporates optimizations to pre-compute and retain in memory as much as possible. phyclass and epa used together finally, we explored whether placement can be improved by using both methods discussed above in conjunction with each other. we found that, using a mixture of equal numbers of query lengths based on the s500r data set, phyclass alone correctly classified 40% of queries, and epa correctly classified 41%. however, for the 32% of the data for which phyclass and epa agreed, correctly or incorrectly, on the placement, 80% is classified correctly. in this way, we are able to roughly double the accuracy rate for about a third of the queries. this dual approach may be considered an advantage over traditional bootstrapping, which is usually conservative and time consuming.  using sequence simulation, we evaluated the use of the minimum evolution principle to place aligned fragmented dna sequences representing metagenomic reads into phylogenetically correct positions in an existing tree of known sequences. our tests showed the accuracy of the new method to be comparable to, but in most cases slightly less than that of the best existing maximum likelihood program to deal with the same problem. consensus assignments based on both approaches together were found to be often more correct than either method individually, even when the statistical support for assignments was low. 
using computer simulations, we assessed the accuracy of the new approach for different read lengths over a variety of data sets and phylogenetic trees. we found the accuracy of the new method to be good and comparable to existing maximum likelihood approaches. without using heuristics, the new approach efficiently finds the optimal placement of the unknown read in a reference phylogenetic tree given a sequence alignment for the taxa in the tree. in particular, we found that the consensus assignments based on me and ml approaches are more correct than either method individually. this is true even when the statistical support for read assignments was low, which is inevitable given that individual reads are often short and come from only one gene. a central problem of computational metagenomics is determining the correct placement into an existing phylogenetic tree of individual reads obtained using next-generation sequencing of dna samples from a mixture of known and unknown species. correct placement allows us to easily identify or classify the sequences in the sample as to taxonomic position or function.
 a central problem of computational metagenomics is determining the correct placement into an existing phylogenetic tree of individual reads obtained using next-generation sequencing of dna samples from a mixture of known and unknown species. correct placement allows us to easily identify or classify the sequences in the sample as to taxonomic position or function.  here we propose a novel method, based on the minimum evolution phylogenetic inference criterion, for determining the appropriate phylogenetic position of each read. without using heuristics, the new approach efficiently finds the optimal placement of the unknown read in a reference phylogenetic tree given a sequence alignment for the taxa in the tree. in short, the total resulting branch length for the tree is computed for every possible placement of the unknown read and the placement that gives the smallest value for this total is the best choice. by taking advantage of computational efficiencies and mathematical formulations, we are able to find the true optimal me placement for each read in the phylogenetic tree. using computer simulations, we assessed the accuracy of the new approach for different read lengths over a variety of data sets and phylogenetic trees. we found the accuracy of the new method to be good and comparable to existing maximum likelihood approaches.  in particular, we found that the consensus assignments based on me and ml approaches are more correct than either method individually. this is true even when the statistical support for read assignments was low, which is inevitable given that individual reads are often short and come from only one gene. 24- november 2nd international genomic medicine conference jeddah, kingdom of saudi arabia 