Oct 17, 2017

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

Xinan LiuJinze Liu


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. 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 algorithms Kraken and Clark, and requires only one-third of the RAM. In comparison to Kaiju, a metagenomic classification tool using protein sequences instead of genomic sequences, MetaOthello is three times faster and exhibits 20-30% higher classification sensitivity. We report comparative analyses of both scalability and accuracy using a number of simulated and empirical datasets. MetaOthello is a stand-alone program implemented in C ++. The current version (...Continue Reading

Mentioned in this Paper

Genome Assembly Sequence
Nucleic Acid Sequencing
Computer Programs and Programming
CCDC26 gene

Related Feeds

CREs: Gene & Cell Therapy

Gene and cell therapy advances have shown promising outcomes for several diseases. The role of cis-regulatory elements (CREs) is crucial in the design of gene therapy vectors. Here is the latest research on CREs in gene and cell therapy.