MAGE: Strain Level Profiling of Metagenome Samples

Metagenomic profiling from sequencing data aims to disentangle a microbial sample at lower ranks of the taxonomy such as species and strains with precise measurement of abundances. State-of-the-art tools for metagenomic profiling often rely on homology based and marker based identification of marker sequences using complex and compute intensive methods. Such approaches often have difficulties in accurate strain level profiling due to limited read support. Furthermore, incorporation of updates to the reference data are expensive. We develop MAGE, which is a non-homology based, non-marker based and alignment free strain level profiling tool for accurate abundance estimation. MAGE works with a k-mer based index of the reference data. MAGE uses a combination of the well-known FM index and R-index, together with an efficient meta-index for constructing a compact and comprehensive index. Using the read mapping results MAGE performs strain level abundance estimations. In order to obtain accurate estimates, MAGE performs a novel local search based optimization which computes maximum likelihood estimates subject to constraints on read coverage. We performed several experiments for strain level profiling, where MAGE showed superior performance compared to the state-of-the-art on a wide range of performance metrics.