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.

Figure 1

Process of counting n-mer frequencies. Given a value for n, the first step is generating all of the n-mer words that are possible. In the next step, we count the number of times that each word appears in the sequence. Finally, we normalize the frequency vector by dividing each number of occurrences by the total number of n-mers.

Figure 2

Configuration scores per taxon for a genomic dataset (d = G). The graph on the left presents the scores for the configuration (G,-, 5, -, c) and graph on the right presents the scores for the configuration (G, -, 5, -, h).

Figure 3

Configuration scores per n-mer word length for the genomic dataset. The graph on the left was generated under the configuration (G, -,-, kl, c), and graph on the right was generated under (G, -,-, kl, h). All of the seven taxonomic levels are considered.

Figure 4

Taxonomic tree. Taxonomic tree for phyla, including Crenarchaeota, Actinobacteria, Bacteroidetes, Thermotogae, and Chlamydiae.

Figure 5

Configuration scores per taxon for the metagenomic synthetic fragments dataset (d = F). The graph on the left was generated under configuration (F, -, 4, -, c) and the graph on the right was generated under configuration (F, -, 4, -, h).

Figure 6

Configuration scores per n-mer word length for the metagenomic dataset. The graph on the left was generated under the configuration (F, -,-, kl, c) and graph on the right was generated under the configuration (F, -,-, kl, h). All of the seven taxonomic levels are considered.

Figure 7

Scores as a function of n and s for a genomic dataset (d = G). The x-axis represents the length of the n-mer sequences. The top graph is the conventional score function (G, sp, -,-, c), and the bottom graph is the hierarchical score function (G, sp, -,-, h).

Figure 8

Scores as a function of n and s for synthetic metagenomic dataset (d = F). The x-axis represents the length of the n-mer sequences. The top graph is the conventional score function (F, sp, -,-, c), and the bottom graph is the hierarchical score function (F, sp, -,-, h).