Co-culture of intestinal organoids with a colibactin-producing pks + E. coli strain (EcC) revealed mutational signatures also found in colorectal cancer (CRC). E. coli Nissle 1917 (EcN) remains a commonly used probiotic, despite harboring the pks operon and inducing double strand DNA breaks. We determine the mutagenicity of EcN and three CRC-derived pks + E. coli strains with an analytical framework based on sequence characteristic of colibactin-induced mutations. All strains, including EcN, display varying levels of mutagenic activity. Furthermore, a machine learning approach attributing individual mutations to colibactin reveals that patients with colibactin-induced mutations are diagnosed at a younger age and that colibactin can induce a specific APC mutation. These approaches allow the sensitive detection of colibactin-induced mutations in ∼12% of CRC genomes and even in whole exome sequencing data, representing a crucial step toward pinpointing the mutagenic activity of distinct pks + E. coli strains. [Display omitted] • Detection of specific mutations induced by pks+ E. coli strains, including Nissle 1917 • Mutation classifier indicates 12% of CRC display colibactin mutagenesis • Colibactin-associated CRC cases have APC mutations at colibactin motifs • Colibactin-CRC cases have a younger age of onset in multiple cohorts In this study, Rosendahl Huber et al. show the mutagenic properties of pks+ E. coli strains, including probiotic E. coli Nissle 1917, using the extended target sequence context of colibactin and with a machine-learning model. These approaches allow for better distinguishing of colibactin-associated colorectal cancer cases, which are younger and are enriched for APC mutations matching the colibactin motif. [ABSTRACT FROM AUTHOR]