{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T20:56:40Z","timestamp":1774731400337,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>Our filtering method for 3C data considers both metric consistency and statistical confidence simultaneously resulting in lower-error embeddings that are biologically more plausible.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1748-7188-8-8","type":"journal-article","created":{"date-parts":[[2013,3,9]],"date-time":"2013-03-09T13:15:10Z","timestamp":1362834910000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Resolving spatial inconsistencies in chromosome conformation measurements"],"prefix":"10.1186","volume":"8","author":[{"given":"Geet","family":"Duggal","sequence":"first","affiliation":[]},{"given":"Rob","family":"Patro","sequence":"additional","affiliation":[]},{"given":"Emre","family":"Sefer","sequence":"additional","affiliation":[]},{"given":"Hao","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Darya","family":"Filippova","sequence":"additional","affiliation":[]},{"given":"Samir","family":"Khuller","sequence":"additional","affiliation":[]},{"given":"Carl","family":"Kingsford","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,3,9]]},"reference":[{"issue":"5558","key":"181_CR1","doi-asserted-by":"publisher","first-page":"1306","DOI":"10.1126\/science.1067799","volume":"295","author":"J Dekker","year":"2002","unstructured":"Dekker J: Capturing chromosome conformation. Science. 2002, 295 (5558): 1306-1311.","journal-title":"Science"},{"issue":"7","key":"181_CR2","doi-asserted-by":"publisher","first-page":"e1002125","DOI":"10.1371\/journal.pcbi.1002125","volume":"7","author":"MA Marti-Renom","year":"2011","unstructured":"Marti-Renom MA, Mirny LA: Bridging the resolution gap in structural modeling of 3D genome organization. PLoS Comput Biol. 2011, 7 (7): e1002125.","journal-title":"PLoS Comput Biol"},{"key":"181_CR3","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1038\/nsmb.1936","volume":"18","author":"D Ba\u00f9","year":"2010","unstructured":"Ba\u00f9 D: The three-dimensional folding of the \u03b1-globin gene domain reveals formation of chromatin globules. Nat Struct & Mol Biol. 2010, 18: 107-114.","journal-title":"Nat Struct & Mol Biol"},{"issue":"5950","key":"181_CR4","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1126\/science.1181369","volume":"326","author":"E Lieberman-Aiden","year":"2009","unstructured":"Lieberman-Aiden E: Comprehensive mapping of long-range interactions reveals folding principles of the human genome. Science. 2009, 326 (5950): 289-293.","journal-title":"Science"},{"key":"181_CR5","doi-asserted-by":"publisher","first-page":"1109","DOI":"10.1038\/nbt.2049","volume":"29","author":"G Fudenberg","year":"2011","unstructured":"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.","journal-title":"Nat Biotechnol"},{"issue":"7296","key":"181_CR6","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1038\/nature08973","volume":"465","author":"Z Duan","year":"2010","unstructured":"Duan Z: A three-dimensional model of the yeast genome. Nature. 2010, 465 (7296): 363-367.","journal-title":"Nature"},{"key":"181_CR7","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1038\/nbt.2057","volume":"30","author":"R Kalhor","year":"2012","unstructured":"Kalhor R: Genome architectures revealed by tethered chromosome conformation capture and population-based modeling. Nat Biotechnol. 2012, 30: 90-98.","journal-title":"Nat Biotechnol"},{"issue":"3","key":"181_CR8","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.cell.2012.01.010","volume":"148","author":"T Sexton","year":"2012","unstructured":"Sexton T: Three-dimensional folding and functional organization principles of the Drosophila genome. Cell. 2012, 148 (3): 458-472.","journal-title":"Cell"},{"issue":"22","key":"181_CR9","doi-asserted-by":"publisher","first-page":"8164","DOI":"10.1093\/nar\/gkq955","volume":"38","author":"H Tanizawa","year":"2010","unstructured":"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.1093\/nar\/gkq955.","journal-title":"Nuc Acids Res"},{"issue":"2","key":"181_CR10","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1016\/j.molcel.2011.09.010","volume":"44","author":"MA Umbarger","year":"2011","unstructured":"Umbarger MA: The three-dimensional architecture of a bacterial genome and its alteration by genetic perturbation. Mol Cell. 2011, 44 (2): 252-264.","journal-title":"Mol Cell"},{"key":"181_CR11","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1038\/nature11279","volume":"489","author":"A Sanyal","year":"2012","unstructured":"Sanyal A, Lajoie BR, Jain G, Dekker J: The long-range interaction landscape of gene promoters. Nat. 2012, 489: 109-113. 10.1038\/nature11279.","journal-title":"Nat"},{"key":"181_CR12","volume-title":"Genome Res","author":"R McCord","year":"2012","unstructured":"McCord R: Correlated alterations in genome organization, histone methylation, and DNA, \u2014 lamina interactions in Hutchinson-Gilford Progeria syndrome. Genome Res. in press 2012."},{"issue":"7398","key":"181_CR13","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1038\/nature11082","volume":"485","author":"J Dixon","year":"2012","unstructured":"Dixon J: Topological domains in mammalian genomes identified by analysis of chromatin interactions. Nature. 2012, 485 (7398): 376-380.","journal-title":"Nature"},{"issue":"11","key":"181_CR14","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1038\/ng.947","volume":"43","author":"E Yaffe","year":"2011","unstructured":"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.","journal-title":"Nat Genet"},{"key":"181_CR15","first-page":"480","volume-title":"17th Allerton Conference in Communications, Control and Computing","author":"J Saxe","year":"1979","unstructured":"Saxe J: Embeddabilityof weighted graphs in k-space is strongly NP-hard. 17th Allerton Conference in Communications, Control and Computing. 1979, 480-489. Monticello: Carnegie-Mellon University, Dept. of Computer Science, 1980."},{"key":"181_CR16","volume-title":"Approximation Algorithms for NP-hard Problems","year":"1997","unstructured":"Approximation Algorithms for NP-hard Problems. Edited by: Hochbaum DS. Boston: PWS Publishing Co., 1997."},{"key":"181_CR17","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier R, Rossmanith P: An efficient fixed-parameter algorithm for 3-Hitting Set. J Discrete Algorithms. 2003, 1: 89-102. 10.1016\/S1570-8667(03)00009-1.","journal-title":"J Discrete Algorithms"},{"key":"181_CR18","volume-title":"Search Methodologies: Introductory, Tutorials in Optimization and Decision Support Techniques","author":"C Gomes","year":"2005","unstructured":"Gomes C, Williams R: Approximation algorithms. Search Methodologies: Introductory, Tutorials in Optimization and Decision Support Techniques. Edited by: Burke EK, Kendall G. 2005, New York: Springer,"},{"key":"181_CR19","doi-asserted-by":"crossref","unstructured":"Rousseau M: Three-dimensional modeling of chromatin structure from interaction frequency data using Markov chain Monte Carlo sampling. BMC Bioinformatics. 2011, 12 (414).","DOI":"10.1186\/1471-2105-12-414"},{"key":"181_CR20","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-642-33122-0_23","volume-title":"Proceedings of the 12th international conference on Algorithms in Bioinformatics","author":"G Duggal","year":"2012","unstructured":"Duggal G, Patro R, Sefer E, Wang H, Filippova D, Khuller S, Kingsford C: Resolving spatial inconsistencies in chromosome conformation data. Proceedings of the 12th international conference on Algorithms in Bioinformatics. 2012, 288-300. WABI\u201912, Berlin, Heidelberg: Springer-Verlag,"},{"issue":"17","key":"181_CR21","doi-asserted-by":"publisher","first-page":"2171","DOI":"10.1093\/bioinformatics\/btl332","volume":"22","author":"DL Theobald","year":"2006","unstructured":"Theobald DL, Wuttke DS: THESEUS: maximum likelihood superpositioning and analysis of macromolecular structures. Bioinformatics. 2006, 22 (17): 2171-2172.","journal-title":"Bioinformatics"},{"issue":"5","key":"181_CR22","doi-asserted-by":"publisher","first-page":"2025","DOI":"10.1073\/pnas.0914187107","volume":"107","author":"P Therizols","year":"2010","unstructured":"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.","journal-title":"Proc Natl Acad Sci USA"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-8-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T23:41:49Z","timestamp":1630539709000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-8-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,3,9]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["181"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-8-8","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,3,9]]},"assertion":[{"value":"21 December 2012","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 February 2013","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 March 2013","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"8"}}