A Genomic Tree-Based Sparse Solver

This article is concerned with improving an existing application of compressive sensing to metagenomics—the Quikr method, where nonnegative sparse recovery is performed using the Lawson Hanson algorithm. To enhance the computational speed of this algorithm, we offer GETS: a GEnomic Tree based Sparse solver. We exploit the inherent structure of the genomic problem to uncover an evolutionary family tree type relationship between the species. This genomic tree enables us to obtain a sparse representation of the problem which is created in the offline stage of GETS, a one time computation. This allows for reduced storage and asymptotic speed ups for our solver via sparse matrix computations. We conclude the article with the results of computational experiments performed with genomic datasets. These experiments illustrate the significant speed ups obtained by GETS over matlab’s implementation of the Lawson Hanson algorithm.