Post-translational modifications of histone residue tails are an important component of genome regulation. It is becoming increasingly clear that the combinatorial presence and absence of various modifications define discrete chromatin states which determine the functional properties of a locus. An emerging experimental goal is to track changes in chromatin state maps across different conditions, such as experimental treatments, cell-types or developmental time points.

Here we present chromstaR, an algorithm for the computational inference of combinatorial chromatin state dynamics across an arbitrary number of conditions. ChromstaR uses a multivariate Hidden Markov Model to determine the number of discrete combinatorial chromatin states using multiple ChIP-seq experiments as input and assigns every genomic region to a state based on the presence/absence of each modification in every condition. Application of chromstaR to datasets comprising four marks in five different stages of hematopoietic cell differentiation shows that only 0.1% of the possible state transitions occur, with dynamic transitions involving only 8.15% of the genome. Furthermore, analysis of the frequency of combinatorial states per cell type shows that less than half of all theoretically possible combinations are actually present, and this percentage becomes as low as 16.4% in datasets comprising seven marks in brain tissue. Our findings reveal a striking sparcity in the combinatorial organization and temporal dynamics of chromatin state maps.