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

Xinan Liu, Ye Yu, Jinze Liu, Jinpeng Liu, Corrine F. Elliott, Chen Qian

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

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 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.

Original languageEnglish
Pages (from-to)171-178
Number of pages8
JournalBioinformatics
Volume34
Issue number1
DOIs
StatePublished - Jan 1 2018

Bibliographical note

Publisher Copyright:
© 2017 The Author.

ASJC Scopus subject areas

  • Statistics and Probability
  • Biochemistry
  • Molecular Biology
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'A novel data structure to support ultra-fast taxonomic classification of metagenomic sequences with k-mer signatures'. Together they form a unique fingerprint.

Cite this