Linking exocellular polysaccharide structures and biosynthetic genes in lactic acid bacteria by combinatorial optimization

Lactic acid bacteria produce exocellular polysaccharides (EPSs) that are important in food and health applications, and their functional properties often depend on their chemical structure. These polysaccharides consist of chained repeat units that are assembled stepwise by multiple glycosyltransferases. However, experimental elucidation of EPS structure is time-consuming and labor-intensive, and sequence-based prediction remains limited because the donor and acceptor specificities of glycosyltransferases are difficult to infer from sequence alone. Here, we present a constrained combinatorial optimization framework that integrates data across multiple strains to associate glycosyltransferases in EPS biosynthetic gene clusters with individual sugar residues in EPS repeat units. The framework is constrained by predicted catalytic mechanisms, published experimental evidence, and shared features of glycosyltransferase repertoires and EPS structures across strains. We applied the approach to 10 EPS repeat unit structures elucidated here by nuclear magnetic resonance (NMR) spectroscopy, including four novel structures, together with 15 previously published structures. Using the currently available data set, we could putatively and uniquely assign 42 of 144 glycosyltransferases (29%) to a single repeat-unit residue and determine donor specificity for 60 of 144 glycosyltransferases (41%). This work improves the mapping of EPS genotype-phenotype relationships in lactic acid bacteria and contributes to advancing genome-based prediction of EPS structure. IMPORTANCE The structure of exocellular polysaccharides produced by lactic acid bacteria is important for their functional roles in food and health applications but remains difficult to predict from genome sequence because glycosyltransferase specificity is hard to infer and structural characterization is slow. By combining new exocellular polysaccharide (EPS) repeat unit structures with a constrained multi-strain computational framework, we obtain a partial mapping between eps genes and polysaccharide structure. This work provides a foundation for genome-based selection of lactic acid bacteria with desirable EPS-related properties.