The complex (Bcc) is a group of bacteria including opportunistic human pathogens. Immunocompromised individuals and cystic fibrosis patients are especially vulnerable to serious infections by these bacteria, motivating the search for compounds with antimicrobial activity against the Bcc. Ubonodin is a lasso peptide with promising activity against Bcc species, working by inhibiting RNA polymerase in susceptible bacteria. We constructed a library of over 90 000 ubonodin variants with 2 amino acid substitutions and used a high-throughput screen and next-generation sequencing to examine the fitness of the entire library, generating the most comprehensive data set on lasso peptide activity so far. This screen revealed information regarding the structure-activity relationship of ubonodin over a large sequence space. Remarkably, the screen identified one variant with not only improved activity compared to wild-type ubonodin but also a submicromolar minimum inhibitory concentration (MIC) against a clinical isolate of the Bcc member . Ubonodin and several of the variants identified in this study had lower MICs against certain Bcc strains than those of many clinically approved antibiotics. Finally, the large library size enabled us to develop DeepLasso, a deep learning model that can predict the RNAP inhibitory activity of an ubonodin variant.