MSC: a metagenomic sequence classification algorithm.

Subrata Saha
Jethro Johnson, The Jackson Laboratory
Soumitra Pal
George M. Weinstock, The Jackson Laboratory
Sanguthevar Rajasekaran


Motivation: Metagenomics is the study of genetic materials directly sampled from natural habitats. It has the potential to reveal previously hidden diversity of microscopic life largely due to the existence of highly parallel and low-cost next-generation sequencing (NGS) technology. Conventional approaches align metagenomic reads onto known reference genomes to identify microbes in the sample. Since such a collection of reference genomes is very large, the approach often needs high-end computing machines with large memory which is not often available to researchers. Alternative approaches follow an alignment-free methodology where the presence of a microbe is predicted using the information about the unique k-mers present in the microbe genomes. However, such approaches suffer from high false positives due to trading off the value of k with the computational resources. In this article we propose a highly efficient metagenomic sequence classification algorithm (MSC) that is a hybrid of both approaches. Instead of aligning reads to the full genomes, MSC aligns reads onto a set of carefully chosen, shorter and highly discriminating model sequences built from the unique k-mers of each of the target sequences.

Results: Microbiome researchers are generally interested in two objectives of a taxonomic classifier: 1) to detect prevalence, i.e., the taxa present in a sample, and 2) to estimate their relative abundances. MSC is primarily designed to detect prevalence and experimental results show that MSC is indeed a more effective and efficient algorithm compared to the other state-of-the-art algorithms in terms of accuracy, memory, and runtime. Moreover, MSC outputs an approximate estimate of the abundances.

Availability: The implementations are freely available for non-commercial purposes. They can be downloaded from