This report describes the sequencing in the Escherichia coli B genome of 36 randomly chosen regions that are present in most or all of the fully sequenced E. coli genomes. The phylogenetic relationships among E. coli strains were examined, and evidence for the horizontal gene transfer and variation in mutation rates was determined. The overall phylogenetic tree indicated that E. coli B and K-12 are the most closely related strains, with E. coli O157:H7 being more distantly related, Shigella flexneri 2a even more, and E. coli CFT073 the most distant strain. Within the B, K-12, and O157:H7 clusters, several regions supported alternative topologies. While horizontal transfer may explain these phylogenetic incongruities, faster evolution at synonymous sites along the O157:H7 lineage was also identified. Further interpretation of these results is confounded by an association among genes showing more rapid evolution and results supporting horizontal transfer. Using genes supporting the B and K-12 clusters, an estimate of the genomic mutation rate from a long-term experiment with E. coli B, and an estimate of 200 generations per year, it was estimated that B and K-12 diverged several hundred thousand years ago, while O157:H7 split off from their common ancestor about 1.5-2 million years ago.