Resolving Spatial Inconsistencies in Chromosome Conformation Data
In Proceedings of 12th Workshop on Algorithms in Bioinformatics (WABI 2012), pp. 288-302.
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.
[pdf] [code]
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.