A novel data structure to support ultra-fast taxonomic classification of metagenomic sequences with k-mer signatures.

ABSTRACT: Motivation:Metagenomic read classification is a critical step in the identification and quantification of microbial species sampled by high-throughput sequencing. Although many algorithms have been developed to date, they suffer significant memory and/or computational costs. Due to the growing popularity of metagenomic data in both basic science and clinical applications, as well as the increasing volume of data being generated, efficient and accurate algorithms are in high demand. Results:We introduce MetaOthello, a probabilistic hashing classifier for metagenomic sequencing reads. The algorithm employs a novel data structure, called l-Othello, to support efficient querying of a taxon using its k-mer signatures. MetaOthello is an order-of-magnitude faster than the current state-of-the-art

SUBMITTER: Liu X 

PROVIDER: S-EPMC5870563 | biostudies-literature | 2018 Jan

REPOSITORIES: biostudies-literature