Assembly of minimally fragmented metagenomic pangenome graphs

Pangenome variation graphs are a powerful tool for representing genetic diversity within and across populations. For comparative and evolutionary genomic analyses leveraging these graph-based structures, it is important that graph topology reflects the underlying phylogenetic and genetic similarities of the genomes embedded within the graph. However, in metagenomic settings these approaches often produce highly fragmented multi-component graphs, hindering comparisons of genomes embedded across different components. This challenge is particularly pronounced for hypervariable viral families like Anelloviridae, whose short circular genomes frustrate existing variation graph construction methods. We present PANIMaSTA (Progressive Average Nucleotide Identity and Maximum Spanning Tree-Based Assembly), a workflow to construct minimally fragmented metagenomic pangenome sequence variation graphs through progressive assembly. The order in which the genomes are incorporated into the graph is informed by a maximum spanning tree (MST) inferred from an all-to-all genome similarity matrix comprised of pairwise Anelloviridae average nucleotide identities (ANI). Applied to over 5,200 diverse Anelloviridae genomes, we construct a sequence variation graph whose graph topology reflects the global genome similarities observed across the ANI matrix. PANIMaSTA constructs minimally fragmented metagenomic pangenome sequence variation graphs that are not achievable with existing methods suitable for similarity-aware sequence-to-graph mapping and downstream genetic analyses across highly diverse genomes.