Decomposition of the S. aureus pangenome reveals evolving genetic repertoire associated with adaptation and virulence

Bacterial pangenomes are mosaics of vertically inherited chromosomal backgrounds and horizontally acquired mobile elements, yet existing analysis methods either assign each genome to a single phylogenetic group or treat genes independently, failing to resolve this composite architecture. Here, we show that non-negative matrix factorization decomposes the accessory pangenome of 1,398 curated Staphylococcus aureus genomes into 24 additive gene modules (“phylons”) that cleanly separate lineage-defining components from mobile genetic element repertoires, achieving 90% reconstruction accuracy with 96% precision. The additive representation, where each genome equals a primary lineage phylon plus one or more mobilome phylons, recovers known biology (clonal complex structure, immune evasion cluster types) and reveals previously uncharacterized structure, including multiple horizontal transfer events linking the CC30 and hybrid ST239 pandemic lineages. Annotation-independent validation with geNomad confirmed that 75–96% of mobilome phylon gene instances physically reside within prophage regions across all 1,398 genomes, while coordinate-level analysis of the remainder revealed prophage boundary effects, chromosomally integrated elements, and composite mobilome architecture rather than false assignments. External validation on 966 independent draft genome assemblies yielded zero false-positive lineage assignments (mean AUC = 0.996) with no dependence on assembly quality, and mobilome phylons discriminated human from livestock hosts and methicillin-resistant from methicillin-susceptible isolates without retraining. A lightweight projection tool, phylon_assign, enables rapid classification of new genomes. The generalization of this framework from Escherichia coli and Enterobacter to Staphylococcus aureus – species with fundamentally different pangenome structures – establishes non-negative matrix factorization as a scalable, organism-agnostic approach for resolving the modular architecture of bacterial pangenomes.