Metagenomics is a new and promising field for the analysis of microbial communities, particularly
the human microbiome. With standard techniques of metagenomic profiling, one can reveal
the influential residents within any sampled microbial community of interest, paving the way for
forms of further exploration. Metagenome comparison is such an avenue of interest, and to combat
the computational infeasibility of alignment-based methods for large samples, k-mer based methods
have been developed to estimate famous measurements of metagenome similarity, such as the
Jaccard Index. However, such methods do not reveal enough information about which organisms
make two metagenomes similar. Such information is important since the notion of metagenome
similarity between two metagenomes implies the presence of common organisms. To address
this shortcoming, we propose a novel graph structure, a Genome-Metagenome Similarity Graph
(GMSG), for modeling containments between various organisms and two metagenomes of interest.
We then explore various functions of these containments to compute measurements of similarity
and distance between two metagenomes.
