Journal
BIOINFORMATICS
Volume 34, Issue 1, Pages 171-178Publisher
OXFORD UNIV PRESS
DOI: 10.1093/bioinformatics/btx432
Keywords
-
Categories
Funding
- National Science Foundation [CAREER award] [1054631, CNS-1701681]
- National Institutes of Health [P30CA177558, 5R01HG006272-03]
- Direct For Computer & Info Scie & Enginr [1054631, 1701681] Funding Source: National Science Foundation
- Division Of Computer and Network Systems [1701681] Funding Source: National Science Foundation
- Div Of Information & Intelligent Systems [1054631] Funding Source: National Science Foundation
Ask authors/readers for more resources
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. Availability and implementation: MetaOthello is a stand-alone program implemented in C++ thornthorn. The current version (1.0) is accessible via https://doi.org/10.5281/zenodo.808941. Contact: liuj@cs.uky.edu Supplementary information: Supplementary data are available at Bioinformatics online.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available