Click
here to close Hello! We notice that
you are using Internet Explorer, which is not supported by Echinobase
and may cause the site to display incorrectly. We suggest using a
current version of Chrome,
FireFox,
or Safari.
Graph rigidity reveals well-constrained regions of chromosome conformation embeddings.
Duggal G
,
Kingsford C
.
???displayArticle.abstract???
BACKGROUND: Chromosome conformation capture experiments result in pairwise proximity measurements between chromosome locations in a genome, and they have been used to construct three-dimensional models of genomic regions, chromosomes, and entire genomes. These models can be used to understand long-range gene regulation, chromosome rearrangements, and the relationships between sequence and spatial location. However, it is unclear whether these pairwise distance constraints provide sufficient information to embed chromatin in three dimensions. A priori, it is possible that an infinite number of embeddings are consistent with the measurements due to a lack of constraints between some regions. It is therefore necessary to separate regions of the chromatin structure that are sufficiently constrained from regions with measurements that do not provide enough information to reconstruct the embedding.
RESULTS: We present a new method based on graph rigidity to assess the suitability of experiments for constructing plausible three-dimensional models of chromatin structure. Underlying this analysis is a new, efficient, and accurate algorithm for finding sufficiently constrained (rigid) collections of constraints in three dimensions, a problem for which there is no known efficient algorithm. Applying the method to four recent chromosome conformation experiments, we find that, for even stringently filtered constraints, a large rigid component spans most of the measured region. Filtering highlights higher-confidence regions, and we find that the organization of these regions depends crucially on short-range interactions.
CONCLUSIONS: Without performing an embedding or creating a frequency-to-distance mapping, our proposed approach establishes which substructures are supported by a sufficient framework of interactions. It also establishes that interactions from recent highly filtered genome-wide chromosome conformation experiments provide an adequate set of constraints for embedding. Pre-processing experimentally observed interactions with this method before relating chromatin structure to biological phenomena will ensure that hypothesized correlations are not driven by the arbitrary choice of a particular unconstrained embedding. The software for identifying rigid components is GPL-Licensed and available for download at http://cbcb.umd.edu/kingsford-group/starfish.
Figure 1. The double-banana graph. The dotted line represents an implied axis of rotation.
Figure 2. Schematic of the body-bar-and-hinge reduction. The rigid body in the dotted line is not included since it does not form a hinge with another body and no bar connects it to another body.
Figure 3. Example chromosome conformation graph. Example augmented chromosome conformation graph. Each node represents a chromosome location and edges represent distance constraints.
Figure 4. Effect of low-frequency interactions on rigid components. (Left) Sizes of rigid subgraphs after removing various percentages of low-frequency interactions for the Duan et al. chromosome conformation graph. The rigid subgraphs at a particular cutoff are sorted and colored by size. The horizontal red line represents the total number of nodes in the chromosome conformation graph before filtering. (Right) The chromosomal locations of rigid components after removing 99.4% of low-frequency interactions. Bars indicate centers of the fragments involved in a rigid component, and colors indicate the various components.
Figure 5. Highlighting structures with rigidity analysis. (A) Confidence in the embedding of the Duan et al. structure. Segments of the genome are colored according to the interaction frequency cutoff at which the segment becomes floppy. Red regions correspond to the 98.8 cutoff% and blue regions are still rigid at the 99.6% cutoff. (B) The Tanizawa et al. structure colored by rigid component for interaction frequency cutoff 99.0%. Dark gray indicates floppy regions. Rigid components in the subtelomeric regions of chromosome 1 are red (see Discussion).
Figure 6. Rigid components after removing short-range interactions. (A) Sum of rigid component sizes after removing all interactions below increasing intra-chromosomal distances (98.8% frequency cutoff). (B) Chromosomal locations of rigid components after removing intra-chromsomal interactions that occur within 75kbp for the Duan et al. chromosome conformation graph (98.8% frequency cutoff). Bars indicate centers of the fragments involved in a rigid component, and colors indicate the various components.
Figure 7. Rigidity of cancer vs. non-cancer graphs. Chromosome locations of rigid components for Lieberman-Aiden et al. (A) lymphoblastoid cell and (B) cancer cell colored by rigid component for interaction frequency cuttoffs 99.4%.
Baù,
The three-dimensional folding of the α-globin gene domain reveals formation of chromatin globules.
2011, Pubmed
Baù,
The three-dimensional folding of the α-globin gene domain reveals formation of chromatin globules.
2011,
Pubmed
Berger,
High-resolution statistical mapping reveals gene territories in live yeast.
2008,
Pubmed
Bystricky,
Long-range compaction and flexibility of interphase chromatin in budding yeast analyzed by high-resolution imaging techniques.
2004,
Pubmed
Cam,
Comprehensive analysis of heterochromatin- and RNAi-mediated epigenetic control of the fission yeast genome.
2005,
Pubmed
Chubynsky,
Algorithms for three-dimensional rigidity analysis and a first-order percolation transition.
2007,
Pubmed
Duan,
A three-dimensional model of the yeast genome.
2010,
Pubmed
Fraser,
Chromatin conformation signatures of cellular differentiation.
2009,
Pubmed
Fudenberg,
High order chromatin architecture shapes the landscape of chromosomal alterations in cancer.
2011,
Pubmed
Jacobs,
Generic rigidity percolation: The pebble game.
1995,
Pubmed
Kalhor,
Genome architectures revealed by tethered chromosome conformation capture and population-based modeling.
2011,
Pubmed
Lieberman-Aiden,
Comprehensive mapping of long-range interactions reveals folding principles of the human genome.
2009,
Pubmed
Marti-Renom,
Bridging the resolution gap in structural modeling of 3D genome organization.
2011,
Pubmed
Rousseau,
Three-dimensional modeling of chromatin structure from interaction frequency data using Markov chain Monte Carlo sampling.
2011,
Pubmed
Sexton,
Three-dimensional folding and functional organization principles of the Drosophila genome.
2012,
Pubmed
Tanizawa,
Mapping of long-range associations throughout the fission yeast genome reveals global genome organization linked to transcriptional regulation.
2010,
Pubmed
Therizols,
Chromosome arm length and nuclear constraints determine the dynamic relationship of yeast subtelomeres.
2010,
Pubmed
Umbarger,
The three-dimensional architecture of a bacterial genome and its alteration by genetic perturbation.
2011,
Pubmed