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.

Gclust: A Parallel Clustering Tool for Microbial Genomic Data Abstract   The accelerating growth of the public microbial genomic data imposes substantial burden on the research community that uses such resources. Building databases for nonredundant reference sequences from massive microbial genomic data based on clustering analysis is essential. However, existing clustering algorithms perform poorly on long genomic sequences. In this article, we present Gclust, a parallel program for clustering complete or draft genomic sequences, where clustering is accelerated with a novel parallelization strategy and a fast sequence comparison algorithm using sparse suffix arrays (SSAs). Moreover, genome identity measures between two sequences are calculated based on their maximal exact matches (MEMs). In this paper, we demonstrate the high speed and clustering quality of Gclust by examining four genome sequence datasets. Gclust is freely available for noncommercial use at  https:github.comniulabgclust . We also introduce a web server for clustering useruploaded genomes at  http:niulab.scgrid.cngclust .