Enterohemorrhagic Escherichia coli (EHEC) O157 are important foodborne pathogens whose major reservoir are asymptomatic cattle. There is evidence suggesting that nonpathogenic E. coli and bacteriophages in the gastro-intestinal tract can influence the pathogenicity of EHEC O157. The factors contributing to the onset and persistence of shedding EHEC O157 in cattle are not completely elucidated. This study used Bayesian network analysis to identify genetic markers of generic E. coli associated with shedding of EHEC O157 in cattle from data generated during an oral experimental challenge study in 4 groups of 6 steers inoculated with three different EHEC O157 strains. The quantification of these associations was accomplished using mixed effects logistic regression. The results showed that the concurrent presence of generic E. coli carrying the prophage marker R4-N and the virulence marker stx2 increased the odds of the onset of EHEC O157 shedding. The presence of prophage markers z2322 and X011C increased, while C1.N decreased the odds of shedding EHEC O157 two days later. A significant antagonist interaction effect between the presence of the virulence marker stx2 on the day of shedding EHEC O157 and two days before shedding was also found. In terms of the persistence of EHEC O157 shedding, the presence of prophage marker R4-N (OR=16, and 95% confidence interval (CI): 1.1, 252) was found to increase the odds of stopping EHEC O157 shedding, whereas prophage marker C1.N (OR=0.16, CI: 0.03, 0.7) and the enterohemolysin gene hly (OR=0.03, CI: 0.001, 0.8) were found to significantly decrease the odds of stopping EHEC O157 shedding. In conclusion, the study found that the presence of certain genetic markers in the generic E. coli genome can influence the pathogenicity of EHEC O157.