We introduce a new method for filtering noisy chromosome
conformation capture (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 algorithms pick high-scoring interactions that obey metric inequalities and can provide a backbone for a more accurate embedding or used in the subsequent analyses.