Metagenome comparison (MC): A new framework for detecting unique/enriched OMUs (operational metagenomic units) derived from whole-genome sequencing reads

Current methods for comparing metagenomes, derived from whole-genome sequencing reads, include top-down metrics or parametric models such as metagenome-diversity, and bottom-up, non-parametric, model-free machine learning approaches like Naïve Bayes for k-mer-profiling. However, both types are limited in their ability to effectively and comprehensively identify and catalogue unique or enriched metagenomic genes, a critical task in comparative metagenomics. This challenge is significant and complex due to its NP-hard nature, which means computational time grows exponentially, or even faster, with the problem size, rendering it impractical for even the fastest supercomputers without heuristic approximation algorithms.