Graph rigidity reveals well-constrained regions of chromosome conformation embeddings.

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 constructingplausible three-dimensional models of chromatin structure. Underlying this analysis is a new, efficient, andaccurate algorithm for finding sufficiently constrained (rigid) collections of constraints in three dimensions, aproblem for which there is no known efficient algorithm. Applying the method to four recent chromosomeconformation experiments, we find that, for even stringently filtered constraints, a large rigid component spansmost of the measured region. Filtering highlights higher-confidence regions, and we find that the organizationof these regions depends crucially on short-range interactions. CONCLUSIONS: Without performing an embedding or creating a frequency-to-distance mapping, our proposed approachestablishes which substructures are supported by a sufficient framework of interactions. It also establishes thatinteractions from recent highly filtered genome-wide chromosome conformation experiments provide anadequate set of constraints for embedding. Pre-processing experimentally observed interactions with thismethod before relating chromatin structure to biological phenomena will ensure that hypothesized correlationsare not driven by the arbitrary choice of a particular unconstrained embedding. The software for identifyingrigid components is GPL-Licensed and available for download at http://cbcb.umd.edu/kingsford-group/starfish.