Resolving spatial inconsistencies in chromosome conformation measurements

Algorithms for Molecular Biology

Geet Duggal²  Rob Patro²  Emre Sefer²  Hao Wang²  Darya Filippova²  Samir Khuller¹  Carl Kingsford² 

[1] Department of Computer Science, University of Maryland, College Park MD 20742, USA

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

关键词: Graph embedding;    Triangle inequality;    Metric violations;    Chromosome conformation capture;    3C;   

Others  :  793454
DOI  :  10.1186/1748-7188-8-8

 received in 2012-12-21, accepted in 2013-02-06,  发布年份 2013

【 摘 要 】

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.

【 授权许可】

   
2013 Duggal et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

Figure 4.

Figure 5.

Figure 6.

【 参考文献 】

• [1]Dekker J: Capturing chromosome conformation. Science 2002, 295(5558):1306-1311.
• [2]Marti-Renom MA, Mirny LA: Bridging the resolution gap in structural modeling of 3D genome organization. PLoS Comput Biol 2011, 7(7):e1002125.
• [3]Baù D: The three-dimensional folding of the α-globin gene domain reveals formation of chromatin globules. Nat Struct & Mol Biol 2010, 18:107-114.
• [4]Lieberman-Aiden E: Comprehensive mapping of long-range interactions reveals folding principles of the human genome. Science 2009, 326(5950):289-293.
• [5]Fudenberg G, Getz G, Meyerson M, Mirny L: High order chromatin architecture shapes the landscape of chromosomal alterations in cancer. Nat Biotechnol 2011, 29:1109-1113.
• [6]Duan Z: A three-dimensional model of the yeast genome. Nature 2010, 465(7296):363-367.
• [7]Kalhor R: Genome architectures revealed by tethered chromosome conformation capture and population-based modeling. Nat Biotechnol 2012, 30:90-98.
• [8]Sexton T: Three-dimensional folding and functional organization principles of the Drosophila genome. Cell 2012, 148(3):458-472.
• [9]Tanizawa H: Mapping of long-range associations throughout the fission yeast genome reveals global genome organization linked to transcriptional regulation. Nuc Acids Res 2010, 38(22):8164-8177.
• [10]Umbarger MA: The three-dimensional architecture of a bacterial genome and its alteration by genetic perturbation. Mol Cell 2011, 44(2):252-264.
• [11]Sanyal A, Lajoie BR, Jain G, Dekker J: The long-range interaction landscape of gene promoters. Nat 2012, 489:109-113.
• [12]McCord R: Correlated alterations in genome organization, histone methylation, and DNA, — lamina interactions in Hutchinson-Gilford Progeria syndrome. Genome Res 2012. in press
• [13]Dixon J: Topological domains in mammalian genomes identified by analysis of chromatin interactions. Nature 2012, 485(7398):376-380.
• [14]Yaffe E, Tanay A: Probabilistic modeling of Hi-C contact maps eliminates systematic biases to characterize global chromosomal architecture. Nat Genet 2011, 43(11):1059-1065.
• [15]Saxe J: Embeddabilityof weighted graphs in k-space is strongly NP-hard. In 17th Allerton Conference in Communications, Control and Computing. Monticello: Carnegie-Mellon University, Dept. of Computer Science, 1980; 1979:480-489.
• [16]Hochbaum DS (Ed): Approximation Algorithms for NP-hard Problems. Boston: PWS Publishing Co.; 1997.
• [17]Niedermeier R, Rossmanith P: An efficient fixed-parameter algorithm for 3-Hitting Set. J Discrete Algorithms 2003, 1:89-102.
• [18]Gomes C, Williams R: Approximation algorithms. In Search Methodologies: Introductory, Tutorials in Optimization and Decision Support Techniques. Edited by Burke EK, Kendall G. New York: Springer; 2005.
• [19]Rousseau M: Three-dimensional modeling of chromatin structure from interaction frequency data using Markov chain Monte Carlo sampling. BMC Bioinformatics 2011., 12(414)
• [20]Duggal G, Patro R, Sefer E, Wang H, Filippova D, Khuller S, Kingsford C: Resolving spatial inconsistencies in chromosome conformation data. In Proceedings of the 12th international conference on Algorithms in Bioinformatics. WABI’12, Berlin, Heidelberg: Springer-Verlag; 2012:288-300.
• [21]Theobald DL, Wuttke DS: THESEUS: maximum likelihood superpositioning and analysis of macromolecular structures. Bioinformatics 2006, 22(17):2171-2172.
• [22]Therizols P: Chromosome arm length and nuclear constraints determine the dynamic relationship of yeast subtelomeres. Proc Natl Acad Sci USA 2010, 107(5):2025-2030.