Motivation: Studies of genetically-distinct individuals have shown that differences in marks of transcriptional regulation such as chromatin accessibility , transcription factor binding and histone modifications are often proximally clustered along the genome. These proximal clusters, which have been labeled as cis-regulatory domains (CRDs), are thought to reflect topological features of the genome and may demarcate functional units linking genetic variation to transcriptional regulation. The problem of distinguishing CRDs from background variation is computationally difficult and current methods rely on greedy approaches with ad-hoc parameters and do not provide an assessment of statistical significance, an important consideration for investigating CRDs in small sample cohorts. Results: We developed a software package, PEAS (Proximal Enrichment by Approximated Sampling), to identify CRDs from a small number of samples (as few as two distinct genetic backgrounds) using a robust statistical approach. PEAS uses methods for efficient and accurate estimation of empirical distributions to quantify the significance of enriched regions, followed by a dynamic programming algorithm to identify the minimum likelihood set of non-overlapping enriched regions. We used it to identify clusters of proximally-enriched differences in the histone mark H3K27ac between two mouse strains as well as proximally-enriched regions of correlation in this mark across five mouse strains. We find that differences in histone acetylation between two mouse strains form significant clusters that overlap closely with differences in the first principal component of their Hi-C correlation matrices. Availability: PEAS is written in Python and is available at https://pypi.org/project/PEAS/. Methods for approximating empirical distributions are implemented in C and Python and are available at https://pypi.org/project/empdist/,