title: Analysis of composition-based metagenomic classification.
abstract: BACKGROUND
  An essential step of a metagenomic study is the taxonomic classification, that is, the identification of the taxonomic lineage of the organisms in a given sample. The taxonomic classification process involves a series of decisions. Currently, in the context of metagenomics, such decisions are usually based on empirical studies that consider one specific type of classifier. In this study we propose a general framework for analyzing the impact that several decisions can have on the classification problem. Instead of focusing on any specific classifier, we define a generic score function that provides a measure of the difficulty of the classification task. Using this framework, we analyze the impact of the following parameters on the taxonomic classification problem: (i) the length of n-mers used to encode the metagenomic sequences, (ii) the similarity measure used to compare sequences, and (iii) the type of taxonomic classification, which can be conventional or hierarchical, depending on whether the classification process occurs in a single shot or in several steps according to the taxonomic tree.
  
  
  RESULTS
  We defined a score function that measures the degree of separability of the taxonomic classes under a given configuration induced by the parameters above. We conducted an extensive computational experiment and found out that reasonable values for the parameters of interest could be (i) intermediate values of n, the length of the n-mers; (ii) any similarity measure, because all of them resulted in similar scores; and (iii) the hierarchical strategy, which performed better in all of the cases.
  
  
  CONCLUSIONS
  As expected, short n-mers generate lower configuration scores because they give rise to frequency vectors that represent distinct sequences in a similar way. On the other hand, large values for n result in sparse frequency vectors that represent differently metagenomic fragments that are in fact similar, also leading to low configuration scores. Regarding the similarity measure, in contrast to our expectations, the variation of the measures did not change the configuration scores significantly. Finally, the hierarchical strategy was more effective than the conventional strategy, which suggests that, instead of using a single classifier, one should adopt multiple classifiers organized as a hierarchy.
authors.affiliation: Laboratório Nacional de Computação Científica, Petrópolis, RJ, Brazil. susan.higashi@inria.fr
authors.forename: Susan
authors.initials: S
authors.lastname: Higashi
authors.forename: André da Motta Salles
authors.initials: Ada M
authors.lastname: Barreto
authors.forename: Maurício Egidio
authors.initials: ME
authors.lastname: Cantão
authors.forename: Ana Tereza Ribeiro
authors.initials: AT
authors.lastname: de Vasconcelos
mesh_terms: D000465:Algorithms; D002965:Classification / Q000379:methods*; D056186:Metagenomics / Q000379:methods*; D008957:Models, Genetic; D010802:Phylogeny; D017385:Sequence Homology