Fast Approximation of Frequent kmers and Applications to Metagenomics Estimating the abundances of all kmers in a set of biological sequences is a fundamental and challenging problem with many applications in biological analysis. While several methods have been designed for the exact or approximate solution of this problem, they all require to process the entire dataset, that can be extremely expensive for highthroughput sequencing datasets. While in some applications it is crucial to estimate all kmers and their abundances, in other situations reporting only frequent kmers, that appear with relatively high frequency in a dataset, may suffice. This is the case, for example, in the computation of kmersxe2x80x99 abundancebased distances among datasets of reads, commonly used in metagenomic analyses.

The Metagenomic Binning Problem: Clustering Markov Sequences The goal of metagenomics is to study the composition of microbial communities, typically using highthroughput shotgun sequencing. In the metagenomic binning problem, we observe random substrings (called contigs) from a mixture of genomes and want to cluster them according to their genome of origin. Based on the empirical observation that genomes of different bacterial species can be distinguished based on their tetranucleotide frequencies, we model this task as the problem of clustering N sequences generated by M distinct Markov processes, where Mll N. Utilizing the largedeviation principle for Markov processes, we establish the informationtheoretic limit for perfect binning. Specifically, we show that the length of the contigs must scale with the inverse of the Chernoff Information between the two most similar species. Our result also implies that contigs should be binned using the conditional relative entropy as a measure of distance, as opposed to the Euclidean distance often used in practice.