Large-scale metagenomic clustering via quasi clique enumeration and read assignment ambiguity resolution

Clustering of metagenomic reads from the set of sampled species at the resolution of a taxonomic level is an important problem in metagenomics. The problem is challenging due to 1) large scale of metagenomic sequence data, and 2) difficulty in distinguishing between homologous reads obtained from different species. In addition, classification at a hierarchy of taxonomic units is important, and it is difficult to judge what level of read similarity is appropriate to achieve the best quality clustering for any given taxonomic unit.