Duggal G and Kingsford C (2012), Graph rigidity reveals well-constrained regions...

ECB-ART-42583

BMC Bioinformatics 2012 Sep 21;13:241. doi: 10.1186/1471-2105-13-241.

Show Gene links Show Anatomy links

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.

???displayArticle.pubmedLink??? 22998471
???displayArticle.pmcLink??? PMC3577487
???displayArticle.link??? BMC Bioinformatics
???displayArticle.grants??? [+]

Genes referenced: LOC115919910 LOC115925415 LOC583082

???attribute.lit??? ???displayArticles.show???

	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%.

References [+] :

Baù, The three-dimensional folding of the α-globin gene domain reveals formation of chromatin globules. 2011, Pubmed