The enormous chemical diversity and strain variability of prokaryotic protein glycosylation makes their large-scale exploration exceptionally challenging. Therefore, despite the universal relevance of protein glycosylation across all domains of life, the understanding of their biological significance and the evolutionary forces shaping oligosaccharide structures remains highly limited. Here, we report on a newly established mass binning glycoproteomics approach that establishes the chemical identity of the carbohydrate components and performs untargeted exploration of prokaryotic oligosaccharides from large-scale proteomics data directly. We demonstrate our approach by exploring an enrichment culture of the globally relevant anaerobic ammonium-oxidizing bacterium Ca. Kuenenia stuttgartiensis. By doing so we resolve a remarkable array of oligosaccharides, which are produced by two seemingly unrelated biosynthetic routes, and which modify the same surface-layer protein simultaneously. More intriguingly, the investigated strain also accomplished modulation of highly specialized sugars, supposedly in response to its energy metabolism—the anaerobic oxidation of ammonium—which depends on the acquisition of substrates of opposite charges. Ultimately, we provide a systematic approach for the compositional exploration of prokaryotic protein glycosylation, and reveal a remarkable example for the evolution of complex oligosaccharides in bacteria.

Nonulosonic acids, commonly referred to as sialic acids, are a highly important group of nine-carbon sugars common to all domains of life. They all share biosynthetic and structural features, but otherwise display a remarkable chemical diversity. In humans, sialic acids cover all cells which makes them important for processes such as cellular protection, immunity and brain development. On the other hand, sialic acids and other nonulosonic acids have been associated with pathological processes including cancer and viral infections. In prokaryotes, nonulosonic acids are commonly associated with pathogens, which developed through molecular mimicry a strategy to circumvent the host's immune response. However, the remarkably large chemical diversity of prokaryotic nonulosonic acids challenges their discovery, and research on molecular characteristics essential for medical applications are often not feasible. Here, we demonstrate a novel, universal large-scale discovery approach that tackles the unmapped diversity of prokaryotic nonulosonic acids. Thereby, we utilize selective chemical labelling combined with a newly established mass spectrometric all-ion-reaction scanning approach to identify nonulosonic acids and other ulosonic acid-like sugars. In doing so, we provide a first molecular-level comparative study on the frequency and diversity across different phyla. We not only illustrate their surprisingly wide-spread occurrence in non-pathogenic species, but also provide evidence of potential higher carbon variants. Many biomedical studies rely on synthetic routes for sialic acids, which are highly demanding and often of low product yields. Our approach enables large-scale exploration for alternative sources of these highly important compounds.