Digital Repository at the University of Maryland (DRUM)  >
College of Computer, Mathematical & Natural Sciences  >
Computer Science  >
Computer Science Research Works 

Please use this identifier to cite or link to this item:

Title: Graph rigidity reveals non-deformable collections of chromosome conformation constraints
Authors: Duggal, Geet
Kingsford, Carl
Type: Preprint
Keywords: Bioinformatics
Graph rigidity
Chromosome conformation
Issue Date: 14-Dec-2011
Abstract: Motivation: 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:
Appears in Collections:Computer Science Research Works

Files in This Item:

File Description SizeFormatNo. of Downloads
starfish.pdf1.63 MBAdobe PDF504View/Open

All items in DRUM are protected by copyright, with all rights reserved.


DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments