Understanding gene function and regulation is essential for the interpretation, prediction, and ultimate design of cell responses to changes in the environment. A multitude of technologies, abstractions, and interpretive frameworks have emerged to answer the challenges presented by genome function and regulatory network inference. Here, we propose a new approach for producing biologically meaningful clusters of coexpressed genes, called <
i>
Atomic Regulons<
/i>
(ARs), based on expression data, gene context, and functional relationships. We demonstrate this new approach by computing ARs for <
i>
Escherichia coli<
/i>
, which we compare with the coexpressed gene clusters predicted by two prevalent existing methods: hierarchical clustering and k-means clustering. We test the consistency of ARs predicted by all methods against expected interactions predicted by the Context Likelihood of Relatedness (CLR) mutual information based method, finding that the ARs produced by our approach show better agreement with CLR interactions. We then apply our method to compute ARs for four other genomes: <
i>
Shewanella oneidensis<
/i>
, <
i>
Pseudomonas aeruginosa<
/i>
, <
i>
Thermus thermophilus<
/i>
, and <
i>
Staphylococcus aureus<
/i>
. We compare the AR clusters from all genomes to study the similarity of coexpression among a phylogenetically diverse set of species, identifying subsystems that show remarkable similarity over wide phylogenetic distances. We also study the sensitivity of our method for computing ARs to the expression data used in the computation, showing that our new approach requires less data than competing approaches to converge to a near final configuration of ARs. We go on to use our sensitivity analysis to identify the specific experiments that lead most rapidly to the final set of ARs for <
i>
E. coli<
/i>
. As a result, this analysis produces insights into improving the design of gene expression experiments.