In line with similar techniques, compressive sensing has the ability to reduce tremensdously tasks based on comparing large sets of large elements (see And so it begins ... Compressive Genomics), here we are looking at reducing the size of the samples through CS techniques in order to fast forward the phylogenic tree construction. Recall that we have potentially 7 billion microbiomes (the following study looks at microbiomes) and most of them are sparse over time. That's a lot of sparse objects to gather and the real question probably becomes, Instead of recognizing it is sparse and producing outstanding method for comparison, maybe we should look at sensors that get the compressed information in the first place. Without further due here is:
Quikr: a Method for Rapid Reconstruction of Bacterial Communities via Compressive Sensing by David Koslicki, Simon Foucart, and Gail Rosen
Abstract. Many metagenomic studies compare hundreds to thousands of environmental and health-related samples by extracting and sequencing their 16S rRNA amplicons and measuring their similarity using beta-diversity metrics. However, one of the ﬁrst steps - to classify the operational taxonomic units withing the sample - can be a computationally time-consuming task since most methods rely on computing the taxonomic assignment of each individual read out of tens to hundreds of thousands of reads. We introduce Quikr: a QUadratic, K-mer based, Iterative,Reconstruction method which computes a vector of taxonomic assignments and their proportions in the sample using an optimization technique motivated from the mathematical theory of compressive sensing. On both simulated and actual biological data, we demonstrate that Quikr istypically more accurate as well as typically orders of magnitude faster than the most commonly utilized taxonomic assignment technique (the Ribosomal Database Project’s Naıve Bayesian Classiﬁer). Furthermore, the technique is shown to be unaﬀected by the presence of chimeras thereby allowing for the circumvention of the time-intensive step of chimera ﬁltering. The Quikr computational package (using MATLAB or Octave) for the Linux and Mac platforms is available at http://sourceforge.net/projects/quikr/.The Quikr page is here while an implementation is available here.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.