Exploring chromatin hierarchical organization via Markov State Modelling

We propose a new computational method for exploring chromatin structural organization based on Markov State Modelling of Hi-C data represented as an interaction network between genomic loci. A Markov process describes the random walk of a traveling probe in the corresponding energy landscape, mimicking the motion of a biomolecule involved in chromatin function. By studying the metastability of the associated Markov State Model upon annealing, the hierarchical structure of individual chromosomes is observed, and corresponding set of structural partitions is identified at each level of hierarchy. Then, the notion of effective interaction between partitions is derived, delineating the overall topology and architecture of chromosomes. Mapping epigenetic data on the graphs of intra-chromosomal effective interactions helps in understanding how chromosome organization facilitates its function. A sketch of whole-genome interactions obtained from the analysis of 539 partitions from all 23 chromosomes, complemented by distributions of gene expression regulators and epigenetic factors, sheds light on the structure-function relationships in chromatin, delineating chromosomal territories, as well as structural partitions analogous to topologically associating domains and active / passive epigenomic compartments. In addition to the overall genome architecture shown by effective interactions, the affinity between partitions of different chromosomes was analyzed as an indicator of the degree of association between partitions in functionally relevant genomic interactions. The overall static picture of whole-genome interactions obtained with the method presented in this work provides a foundation for chromatin structural reconstruction, for the modelling of chromatin dynamics, and for exploring the regulation of genome function. The algorithms used in this study are implemented in a freely available Python package ChromaWalker (https://bitbucket.org/ZhenWahTan/chromawalker).Author summary: A new era in chromatin research started with the availability of Hi-C data and new experimental techniques driving improvements in data resolution enable us to achieve a deeper understanding of the chromatin structure and function, while calling, at the same time, for the development of more advanced analytical methods. Though instrumental in the analysis of Hi-C data, both model-driven polymer models and data-driven statistical approaches are always based on several assumptions and require tweaking parameters. We interpret the Hi-C frequencies of chromatin interactions in terms of pairwise contact energies, obtaining corresponding energy landscape that represents the structure and interactions in chromatin. The ruggedness of this landscape is explored by the random walk of a travelling probe, which is formalized in the framework of a Markov State Model. The multilevel energy landscape induces metastability in the Markov process, revealing the hierarchy of chromatin structural organization. Structural partitions determined by the basins in the energy landscape are, thus, naturally obtained at different levels of hierarchy without any preliminary assumptions. Effective interactions between partitions are evaluated, providing a blueprint of the whole-genome organization and functional interactions, which is further substantiated by mapping of information on gene expression regulators and different epigenetic factors. The notion of affinity between partitions complements the picture by reflecting the degrees of association between partitions, calling for the modelling of chromatin dynamics and exploring its functional modulation.