Resolving spatial inconsistencies in chromosome conformation measurements

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.

Figure 1

Metric filtering performance on various chromosomes of yeast. The total confidence that each algorithm recovers normalized by the total number of edges is plotted. Higher values are better. The objective value of the linear program (blue diamonds) gives an upper bound for both the ConsT and ConsP solutions. We also compare our algorithms to the Duan et al. filtering method at FDR 1% (black circles) which is their largest and highest-confidence filtered interaction set. (A bug in the SP-Union script in the conference version of this paper [20] erroneously led to plotting the sum of edge q-values instead of the sum of confidence. The plots have been updated to correctly plot total confidence with little qualitative difference).

Figure 2

Filtered graphs embedded in 3D. Superposition of 10 embeddings for both ConsT and C-Rank filterings. (a)Set-Cover. (b)C-Rank of the same size as the Set-Cover. (c)Set-Cover after removing ≈20% of the lowest-confidence edges.

Figure 3

Histogram of genomic distances and interaction confidences between C-Rank and ConsT. Distances and confidences for both filtering methods were computed on the intra-chromosomal interactions. (a) The ConsT filtering kept more low-confidence edges than C-Rank (“FDR Filter” in the legend). (b) The ConsT filtering kept interactions with larger genomic distances than C-Rank..

Figure 4

Intersections among metric edge sets.

Figure 5

Total and normalized surprises of included edges vs.ρ. Total confidences (top) and normalized confidences (bottom) of included edges for different metric filtering algorithms on yeast chromosome 1 dataset. Normalized confidence is the total confidence divided by the number of edges in the output graph.

Figure 6

Distribution of edge violation magnitudes. Histogram of d(u,w)−[d(u,v)+d(v,w)] for all edges {u,w} in violating triangles in the original graph (total bar height) and the number of these edges that are included in the filtered graph when ρ=0 using the Set-Cover filtering (yellow portion). The blue portion of the bar represents the number of edges that are filtered out when ρ=0.