Maximum parsimony interpretation of chromatin capture experiments

Autoři: Dirar Homouz aff001;  Andrzej S. Kudlicki aff004
Působiště autorů: Department of Physics, Khalifa University of Science and Technology, Abu Dhabi, UAE aff001;  Department of Physics, University of Houston, Houston, TX, United States of America aff002;  Center for Theoretical Biological Physics, Rice University, Houston, TX, United States of America aff003;  Institute for Translational Sciences, University of Texas Medical Branch, Galveston, TX, United States of America aff004;  Department of Biochemistry and Molecular Biology, University of Texas Medical Branch, Galveston, TX, United States of America aff005
Vyšlo v časopise: PLoS ONE 14(11)
Kategorie: Research Article
doi: 10.1371/journal.pone.0225578


We present a new approach to characterizing the global geometric state of chromatin from HiC data. Chromatin conformation capture techniques (3C, and its variants: 4C, 5C, HiC, etc.) probe the spatial structure of the genome by identifying physical contacts between genomic loci within the nuclear space. In whole-genome conformation capture (HiC) experiments, the signal can be interpreted as spatial proximity between genomic loci and physical distances can be estimated from the data. However, observed spatial proximity signal does not directly translate into persistent contacts within the nuclear space. Attempts to infer a single conformation of the genome within the nuclear space lead to internal geometric inconsistencies, notoriously violating the triangle inequality. These inconsistencies have been attributed to the stochastic nature of chromatin conformation or to experimental artifacts. Here we demonstrate that it can be explained by a mixture of cells, each in one of only several conformational states, contained in the sample. We have developed and implemented a graph-theoretic approach that identifies the properties of such postulated subpopulations. We show that the geometrical conflicts in a standard yeast HiC dataset, can be explained by only a small number of homogeneous populations of cells (4 populations are sufficient to reconcile 95,000 most prominent impossible triangles, 8 populations can explain 375,000 top geometric conflicts). Finally, we analyze the functional annotations of genes differentially interacting between the populations, suggesting that each inferred subpopulation may be involved in a functionally different transcriptional program.

Klíčová slova:

Functional genomics – Genetic loci – Genome annotation – Genomic signal processing – Chromatin – Structural genomics – Transcriptional control – Yeast


1. Lieberman-Aiden E, van Berkum NL, Williams L, Imakaev M, Ragoczy T, Telling A, et al. Comprehensive Mapping of Long-Range Interactions Reveals Folding Principles of the Human Genome. Science. 2009;326(5950):289–93. ISI:000270599500043. doi: 10.1126/science.1181369 19815776

2. Dekker J, Rippe K, Dekker M, Kleckner N. Capturing chromosome conformation. Science. 2002;295(5558):1306–11. ISI:000173926000047. doi: 10.1126/science.1067799 11847345

3. Simonis M, Klous P, Splinter E, Moshkin Y, Willemsen R, de Wit E, et al. Nuclear organization of active and inactive chromatin domains uncovered by chromosome conformation capture-on-chip (4C). Nature Genetics. 2006;38(11):1348–54. ISI:000241592700026. doi: 10.1038/ng1896 17033623

4. Zhao Z, Tavoosidana G, Sjolinder M, Gondor A, Mariano P, Wang S, et al. Circular chromosome conformation capture (4C) uncovers extensive networks of epigenetically regulated intra- and interchromosomal interactions. Nature Genetics. 2006;38(11):1341–7. ISI:000241592700025. doi: 10.1038/ng1891 17033624

5. Dekker J. The three 'C's of chromosome conformation capture: controls, controls, controls. Nat Methods. 2006;3(1):17–21. doi: 10.1038/nmeth823 ISI:000234528000011. 16369547

6. Duan Z, Andronescu M, Schutz K, McIlwain S, Kim YJ, Lee C, et al. A three-dimensional model of the yeast genome. Nature. 2010;465(7296):363–7. doi: 10.1038/nature08973 ISI:000277829200044. 20436457

7. Bystricky K, Heun P, Gehlen L, Langowski J, Gasser SM. Long-range compaction and flexibility of interphase chromatin in budding yeast analyzed by high-resolution imaging techniques. Proceedings of the National Academy of Sciences of the United States of America. 2004;101(47):16495–500. ISI:000225347400023. doi: 10.1073/pnas.0402766101 15545610

8. Rosa A, Maddocks JH, Neumann FR, Gasser SM, Stasiak A. Measuring limits of telomere movement on nuclear envelope. Biophys J. 2006;90(3):L24–6. doi: 10.1529/biophysj.105.077974 16339888; PubMed Central PMCID: PMC1367126.

9. Heun P, Laroche T, Shimada K, Furrer P, Gasser SM. Chromosome dynamics in the yeast interphase nucleus. Science. 2001;294(5549):2181–6. doi: 10.1126/science.1065366 11739961.

10. Kim S, Liachko I, Brickner DG, Cook K, Noble WS, Brickner JH, et al. The dynamic three-dimensional organization of the diploid yeast genome. Elife. 2017;6. doi: 10.7554/eLife.23623 28537556; PubMed Central PMCID: PMC5476426.

11. Duan Z, Andronescu M, Schutz K, McIlwain S, Kim YJ, Lee C, et al. A three-dimensional model of the yeast genome. Nature. 465(7296):363–7. doi: 10.1038/nature08973 ISI:000277829200044. 20436457

12. Duggal G, Patro R, Sefer E, Wang H, Filippova D, Khuller S, et al. Resolving spatial inconsistencies in chromosome conformation measurements. Algorithms for Molecular Biology. 2013;8. ISI:000319000700001.

13. Bolzer A, Kreth G, Solovei I, Koehler D, Saracoglu K, Fauth C, et al. Three-dimensional maps of all chromosomes in human male fibroblast nuclei and prometaphase rosettes. Plos Biology. 2005;3(5):826–42. ISI:000229125400012.

14. de Wit E, de Laat W. A decade of 3C technologies: insights into nuclear organization. Genes Dev. 26(1):11–24. Epub 2012/01/05. 26/1/11 [pii] doi: 10.1101/gad.179804.111 22215806; PubMed Central PMCID: PMC3258961.

15. Benedetti F, Dorier J, Burnier Y, Stasiak A. Models that include supercoiling of topological domains reproduce several known features of interphase chromosomes. Nucleic Acids Res. 2014;42(5):2848–55. doi: 10.1093/nar/gkt1353 24366878; PubMed Central PMCID: PMC3950722.

16. Liu L, Kim MH, Hyeon C. Heterogeneous Loop Model to Infer 3D Chromosome Structures from Hi-C. Biophys J. 2019;117(3):613–25. doi: 10.1016/j.bpj.2019.06.032 31337548; PubMed Central PMCID: PMC6697451.

17. Finn EH, Pegoraro G, Brandao HB, Valton AL, Oomen ME, Dekker J, et al. Extensive Heterogeneity and Intrinsic Variation in Spatial Genome Organization. Cell. 2019;176(6):1502–15 e10. doi: 10.1016/j.cell.2019.01.020 30799036; PubMed Central PMCID: PMC6408223.

18. Mehrotra A, Trick MA. A column generation approach for graph coloring. informs Journal on Computing. 1996;8(4):344–54.

19. Trick MA. Available from:

20. Brélaz D. New methods to color the vertices of a graph. Communications of the ACM. 1979;22(4):251–6.

21. Auerbach RK, Euskirchen G, Rozowsky J, Lamarre-Vincent N, Moqtaderi Z, Lefrancois P, et al. Mapping accessible chromatin regions using Sono-Seq. Proc Natl Acad Sci U S A. 2009;106(35):14926–31. doi: 10.1073/pnas.0905443106 19706456; PubMed Central PMCID: PMC2736440.

22. Homouz D, Kudlicki A. The 3D Organization of the Yeast Genome Correlates with Co-Expression and Reflects Functional Relations between Genes. Plos One. 2013;8(1):e54699. doi: 10.1371/journal.pone.0054699 23382942

23. Liu C, Wang C, Wang G, Becker C, Zaidem M, Weigel D. Genome-wide analysis of chromatin packing in Arabidopsis thaliana at single-gene resolution. Genome Res. 2016;26(8):1057–68. doi: 10.1101/gr.204032.116 27225844; PubMed Central PMCID: PMC4971768.

24. Dong X, Li C, Chen Y, Ding G, Li Y. Human transcriptional interactome of chromatin contribute to gene co-expression. BMC Genomics. 2010;11:704. doi: 10.1186/1471-2164-11-704 21156067; PubMed Central PMCID: PMC3053592.

25. Babaei S, Mahfouz A, Hulsman M, Lelieveldt BP, de Ridder J, Reinders M. Hi-C Chromatin Interaction Networks Predict Co-expression in the Mouse Cortex. PLoS Comput Biol. 2015;11(5):e1004221. doi: 10.1371/journal.pcbi.1004221 25965262; PubMed Central PMCID: PMC4429121.

26. Rutledge MT, Russo M, Belton JM, Dekker J, Broach JR. The yeast genome undergoes significant topological reorganization in quiescence. Nucleic Acids Res. 2015;43(17):8299–313. doi: 10.1093/nar/gkv723 26202961; PubMed Central PMCID: PMC4787801.

27. Rowicka M, Kudlicki A, Tu BP, Otwinowski Z. High-resolution timing of cell cycle-regulated gene expression. Proceedings of the National Academy of Sciences of the United States of America. 2007;104(43):16892–7. doi: 10.1073/pnas.0706022104 ISI:000250487600032. 17827275

28. Tu BP, Kudlicki A, Rowicka M, McKnight SL. Logic of the yeast metabolic cycle: Temporal compartmentalization of cellular processes. Science. 2005;310(5751):1152–8. doi: 10.1126/science.1120499 ISI:000233437300037. 16254148

29. Aymard F, Aguirrebengoa M, Guillou E, Javierre BM, Bugler B, Arnould C, et al. Genome-wide mapping of long-range contacts unveils clustering of DNA double-strand breaks at damaged active genes. Nature structural & molecular biology. 2017;24(4):353–61. Epub 2017/03/07. doi: 10.1038/nsmb.3387 28263325; PubMed Central PMCID: PMC5385132.

30. Biernacka A, Zhu Y, Skrzypczak M, Forey R, Pardo B, Grzelak M, et al. i-BLESS is an ultra-sensitive method for detection of DNA double-strand breaks. Commun Biol. 2018;1:181. Epub 2018/11/06. doi: 10.1038/s42003-018-0165-9 30393778; PubMed Central PMCID: PMC6208412.

31. Crosetto N, Mitra A, Silva MJ, Bienko M, Dojer N, Wang Q, et al. Nucleotide-resolution DNA double-strand break mapping by next-generation sequencing. Nat Methods. 2013;10(4):361–5. Epub 2013/03/19. doi: 10.1038/nmeth.2408 23503052; PubMed Central PMCID: PMC3651036.

32. Giorgetti L, Galupa R, Nora EP, Piolot T, Lam F, Dekker J, et al. Predictive polymer modeling reveals coupled fluctuations in chromosome conformation and transcription. Cell. 2014;157(4):950–63. doi: 10.1016/j.cell.2014.03.025 24813616; PubMed Central PMCID: PMC4427251.

33. Nora EP, Lajoie BR, Schulz EG, Giorgetti L, Okamoto I, Servant N, et al. Spatial partitioning of the regulatory landscape of the X-inactivation centre. Nature. 2012;485(7398):381–5. doi: 10.1038/nature11049 22495304; PubMed Central PMCID: PMC3555144.

Článek vyšel v časopise


2019 Číslo 11