Show simple item record

Graph rigidity reveals non-deformable collections of chromosome conformation constraints

dc.contributor.authorDuggal, Geet
dc.contributor.authorKingsford, Carl
dc.description.abstractMotivation: The physical structure of chromatin is associated with a variety of biological phenomena including long-range regulation, chromosome rearrangements, and somatic copy number alterations. Chromosome conformation capture is a recent experimental technique that results in pairwise proximity measurements between chromosome locations in a genome. This information can be used to construct three-dimensional models of portions of chromosomes or entire genomes using a variety of recently proposed algorithms. However, it is possible that these distance measurements do not provide the proper constraints to uniquely specify such an embedding. It is therefore necessary to separate regions of the chromatin structure that are sufficiently constrained from regions with measurements that suggest a more pliable structure. This separation will allow studies of correlations betweeen chromatin organization and genome function to be targeted to the sufficiently constrained, high-confidence substructures within an embedding. Results: Using rigidity theory, we introduce a novel, fast algorithm for identifying high-confidence (rigid) substructures within graphs that result from chromosome conformation capture experiments. We apply the method to four recent chromosome conformation capture data sets and find that for even stringently filtered experimental constraints, a large rigid region spans most of the genome. We find that the organization of rigid components depends crucially on short-range interactions within the genome. We also find that rigid component boundaries appear at regions associated with areas of low nucleosome density and that properties of rigid, subtelomeric regions are consistent with light microscopy data. Availability: The software for identifying rigid components is GPL-Licensed and available for download at Contact: carlk@cs.umd.eduen_US
dc.description.sponsorshipThis work was supported by the National Science Foundation [CCF-1053918, EF-0849899, and IIS-0812111 to C.K]; the National Institutes of Health [1R21AI085376 to C.K.]; and a Univeristy of Maryland Institute for Advanced Studies New Frontiers Award to C.K.en_US
dc.subjectGraph rigidityen_US
dc.subjectChromosome conformationen_US
dc.titleGraph rigidity reveals non-deformable collections of chromosome conformation constraintsen_US
dc.relation.isAvailableAtCollege of Computer, Mathematical & Natural Sciencesen_us
dc.relation.isAvailableAtComputer Scienceen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us

Files in this item


This item appears in the following Collection(s)

Show simple item record