Email updates

Keep up to date with the latest news and content from Algorithms for Molecular Biology and BioMed Central.

Open Access Research

Resolving spatial inconsistencies in chromosome conformation measurements

Geet Duggal1, Rob Patro1, Emre Sefer1, Hao Wang1, Darya Filippova1, Samir Khuller2 and Carl Kingsford1*

Author Affiliations

1 Lane Center for Computational Biology, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA

2 Department of Computer Science, University of Maryland, College Park MD 20742, USA

For all author emails, please log on.

Algorithms for Molecular Biology 2013, 8:8  doi:10.1186/1748-7188-8-8

Published: 9 March 2013

Abstract

Background

Chromosome structure is closely related to its function and Chromosome Conformation Capture (3C) is a widely used technique for exploring spatial properties of chromosomes. 3C interaction frequencies are usually associated with spatial distances. However, the raw data from 3C experiments is an aggregation of interactions from many cells, and the spatial distances of any given interaction are uncertain.

Results

We introduce a new method for filtering 3C interactions that selects subsets of interactions that obey metric constraints of various strictness. We demonstrate that, although the problem is computationally hard, near-optimal results are often attainable in practice using well-designed heuristics and approximation algorithms. Further, we show that, compared with a standard technique, this metric filtering approach leads to (a) subgraphs with higher statistical significance, (b) lower embedding error, (c) lower sensitivity to initial conditions of the embedding algorithm, and (d) structures with better agreement with light microscopy measurements. Our filtering scheme is applicable for a strict frequency-to-distance mapping and a more relaxed mapping from frequency to a range of distances.

Conclusions

Our filtering method for 3C data considers both metric consistency and statistical confidence simultaneously resulting in lower-error embeddings that are biologically more plausible.

Keywords:
3C; Chromosome conformation capture; Metric violations; Triangle inequality; Graph embedding