Kraken-style taxonomic classification by RTL path scoring

Each query k-mer maps (via the database) to the lowest common ancestor taxon of the genomes containing it; unmapped k-mers are ignored. Hit taxa and their ancestors form a pruned classification tree weighted by hit counts. Every root-to-leaf (RTL) path is scored by the sum of node weights along it; the query is assigned the leaf of the maximal RTL path, with ties resolved to the LCA of the tied leaves. No hits leaves the query unclassified (taxon 0). Kraken 2 applies the same classification step to minimizer-based LCA hits.

Usage

Taxass(kmer_taxa, parent)

Arguments

kmer_taxa

Integer taxon id hit by each k-mer (0 = no hit).

parent

Named vector or list mapping taxon id to parent id; the root maps to itself.

Value

List with taxon, leaf_scores, weights, n_kmers, n_hit, method.

References

Wood, D. E. and Salzberg, S. L. (2014), Kraken: ultrafast metagenomic sequence classification using exact alignments, Genome Biology 15(3), R46. Sequence classification algorithm (RTL scoring, tie to LCA), p. 8 and Figure 1. Wood, D. E., Lu, J. and Langmead, B. (2019), Improved metagenomic analysis with Kraken 2, Genome Biology 20, 257, Methods.

Examples

# taxonomy 1 (root) -> 2 -> 3 and 2 -> 4; most k-mers hit 3
parent <- c(`1` = 1, `2` = 1, `3` = 2, `4` = 2)
Taxass(kmer_taxa = c(3, 3, 3, 4, 0, 2), parent = parent)$taxon
#> [1] 3