Comparative approach to computer analysis of regulatory signals allows one to predict new signals in bacterial genomes with high accuracy. A prediction is reliable whenever candidate signals are consistently observed in several related genomes. We applied comparative approach to the analysis of the Fnr regulon of gamma-proteobacteria. Responding to changes in the aerobic/anaerobic state of the medium, the transcriptional factor Fnr regulates expression of many genes. We predicted Fnr binding-sites in 12 genes regulated by Fnr, and identified 17 new operons as potential members of the Fnr regulon of Escherichia coli. In addition, we described the Fnr regulon of other gamma-proteobacteria.