Comparative metagenomics using pan-metagenomic graphs

Izaak Coleman, Natalya Mametyarova, Andrey Zaznaev, Peiwen Cai, Lisa Yu, Yoli Meydan, Aviya Litman, Ayushi Sharma, Lily He, Amanda Simkhovich, Dwayne Seeram, Heekuk Park, Yael R. Nobel, Aya Brown Kav, Itsik Pe’er, Anne‐Catrin Uhlemann, Tal KorembioRxiv 2025 · DOI

Abstract: Identifying microbial genomic factors underlying human phenotypes is a key goal of microbiome research. Sequence graphs are a highly effective tool for genome comparisons because they enable high-resolution de novo analyses that capture and contextualize complex genomic variation. However, applying sequence graphs to complex microbial communities remains challenging due to the scale and complexity of metagenomic data. Here, we present copangraph, a multi-sample sequence-graph-based analysis framework for comprehensive comparisons of genomic variation across metagenomes. Copangraph uses a novel homology-based graph, which provides both non-arbitrary, evolutionary-motivated grouping of sequences into the same node as well as flexibility in the scale of variation represented by the graph. Its construction relies on hybrid coassembly, a new coassembly approach in which single-sample graphs are first constructed separately and are then merged to create a multi-sample graph. Our results demonstrate that copangraph captures sequence and variant information more accurately than alternative methods, provides graphs that are more suitable for comparative analysis than de Bruijn graphs, and is computationally tractable.

The Challenge of Comparative Metagenomics

Microbiomes are not merely collections of species; they are dynamic populations of similar but non-identical strains. Understanding how these microbes influence human health requires comparative metagenomics: the ability to identify specific genomic differences—such as toxin genes or structural rearrangements—that distinguish one microbiome from another.

Current methodologies face a significant hurdle. Traditional "coassembly," which pools all DNA reads from all samples, is computationally intensive and often yields low-quality results due to data heterogeneity. Conversely, "coarse-graining" methods simplify data to the point of losing critical strain-level details. Copangraph addresses this "missing middle" by providing a scalable and precise way to represent the pan-metagenome—the collective genetic diversity across all samples.

The Copangraph Framework

The authors introduce copangraph, a framework that shifts the paradigm of metagenomic analysis through three primary innovations.

The copangraph construction workflow: individual sequence graphs are clustered into homology groups and then reconstructed into a unified multi-sample copangraph.
  1. Hybrid Coassembly: Instead of pooling raw reads, copangraph assembles each sample individually to create single-sample graphs. It then employs a novel algorithm using paired-end reads to detect "contiguity," linking genomic segments that the initial assembler might have fragmented.
  2. Tunable Homology Merging: Single-sample graphs are merged into a multi-sample graph based on a user-defined homology threshold (e.g., 99% sequence identity). This allows researchers to adjust the resolution of evolutionary relationships, collapsing nearly identical sequences while maintaining distinctions between divergent ones.
  3. Mosaic Repeat Resolution: To handle "intransitive" alignments (where A matches B and B matches C, but A does not match C), copangraph uses an iterative algorithm to resolve mosaic repeats. This ensures the graph structure reflects biological reality rather than technical artifacts.

Capturing Complex Variation

In sequence graphs, strain variations typically manifest as "bubbles"—paths that diverge and subsequently converge. Copangraph's ability to detect these bubbles across samples allows for the identification of specific gene variants associated with clinical outcomes.

A large-scale pan-metagenomic graph generated by copangraph, illustrating complex multi-taxon events and significant within-taxon heterogeneity.

Unlike traditional de Bruijn graphs, where increasing resolution often leads to fragmentation, copangraph decouples homology thresholds from graph complexity. This enables high-resolution comparisons without compromising graph manageability. Furthermore, because it is a de novo method, copangraph can discover genetic elements absent from existing databases, which is vital for exploring the "dark matter" of the microbiome.

Performance and Clinical Utility

The researchers validated copangraph using simulated metagenomes, long-read benchmarks, and clinical cohorts (Colorectal Cancer, Preterm Birth, and VRE colonization). Key results include:

  • Superior Accuracy: Copangraph outperformed tools like MEGAHIT and MetaCarvel in "connectivity F-score," accurately representing genomic linkages.
  • Scalability: The construction process scales linearly with the number of samples, proving faster and more memory-efficient than traditional assemblers for cohorts of 20 to 100 samples.
  • Clinical Prediction: In predicting Vancomycin-resistant Enterococcus (VRE) colonization, copangraph achieved an auROC of 0.76, significantly outperforming taxonomic abundances (0.38) and functional gene profiles (0.59). It identified specific prophages and gene variants (e.g., a class I SAM-dependent methyltransferase) linked to infection clearance.

Future Directions

While copangraph currently utilizes a single constant homology threshold, future iterations may incorporate adaptive thresholds that adjust based on local graph topology or specific taxa. Additionally, the authors suggest that merging graphs based on protein sequence homology or language-model embeddings could reveal even deeper functional similarities across the pan-metagenome.

Summary updated

Abstract

Identifying microbial genomic factors underlying human phenotypes is a key goal of microbiome research. Sequence graphs are a highly effective tool for genome comparisons because they enable high-resolution de novo analyses that capture and contextualize complex genomic variation. However, applying sequence graphs to complex microbial communities remains challenging due to the scale and complexity of metagenomic data. Existing multi-sample sequence graphs used in these settings are highly complex, computationally expensive, less accurate than single-sample alternatives, and often involve arbitrary coarse-graining. Here, we present copangraph, a multi-sample sequence-graph-based analysis framework for comprehensive comparisons of genomic variation across metagenomes. Copangraph uses a novel homology-based graph, which provides both non-arbitrary, evolutionary-motivated grouping of sequences into the same node as well as flexibility in the scale of variation represented by the graph. Its construction relies on hybrid coassembly, a new coassembly approach in which single-sample graphs are first constructed separately and are then merged to create a multi-sample graph. We also present an algorithm that uses paired-end reads to improve detection of contiguous genomic regions, increasing accuracy. Our results demonstrate that copangraph captures sequence and variant information more accurately than alternative methods, provides graphs that are more suitable for comparative analysis than de Bruijn graphs, and is computationally tractable. We show that copangraph reflects meaningful metagenomic variation across diverse scenarios. Importantly, it enables significantly better performance than other metagenomic representations when predicting the gut colonization trajectories of Vancomycin-resistant Enterococcus. Our results underscore the value of our multi-sample, graph-based framework for comparative metagenomic analyses.
BibTeX
@misc{coleman2025comparative,
  author = {Izaak Coleman and Natalya Mametyarova and Andrey Zaznaev and Peiwen Cai and Lisa Yu and Yoli Meydan and Aviya Litman and Ayushi Sharma and Lily He and Amanda Simkhovich and Dwayne Seeram and Heekuk Park and Yael R. Nobel and Aya Brown Kav and Itsik Pe’er and Anne‐Catrin Uhlemann and Tal Korem},
  title = {{Comparative metagenomics using pan-metagenomic graphs}},
  year = {2025},
  doi = {10.1101/2025.11.24.690211},
  howpublished = {bioRxiv},
}
Figure