{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T07:45:10Z","timestamp":1770536710868,"version":"3.49.0"},"reference-count":32,"publisher":"Oxford University Press (OUP)","issue":"22","license":[{"start":{"date-parts":[[2021,5,22]],"date-time":"2021-05-22T00:00:00Z","timestamp":1621641600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"German Federal Ministry of Education and Research","award":["031 A538A"],"award-info":[{"award-number":["031 A538A"]}]},{"name":"German Federal Ministry of Education and Research","award":["031 L0101C de. NBI-epi"],"award-info":[{"award-number":["031 L0101C de. NBI-epi"]}]},{"DOI":"10.13039\/501100001659","name":"German Research Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Germany\u2019s Excellence Strategy","award":["CIBSS\u2014EXC-2189"],"award-info":[{"award-number":["CIBSS\u2014EXC-2189"]}]},{"name":"Germany\u2019s Excellence Strategy","award":["390939984"],"award-info":[{"award-number":["390939984"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,11,18]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Hi-C technology provides insights into the 3D organization of the chromatin, and the single-cell Hi-C method enables researchers to gain knowledge about the chromatin state in individual cell levels. Single-cell Hi-C interaction matrices are high dimensional and very sparse. To cluster thousands of single-cell Hi-C interaction matrices, they are flattened and compiled into one matrix. Depending on the resolution, this matrix can have a few million or even billions of features; therefore, computations can be memory intensive. We present a single-cell Hi-C clustering approach using an approximate nearest neighbors method based on locality-sensitive hashing to reduce the dimensions and the computational resources.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>The presented method can process a 10\u2009kb single-cell Hi-C dataset with 2600 cells and needs 40 GB of memory, while competitive approaches are not computable even with 1 TB of memory. It can be shown that the differentiation of the cells by their chromatin folding properties and, therefore, the quality of the clustering of single-cell Hi-C data is advantageous compared to competitive algorithms.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The presented clustering algorithm is part of the scHiCExplorer, is available on Github https:\/\/github.com\/joachimwolff\/scHiCExplorer, and as a conda package via the bioconda channel. The approximate nearest neighbors implementation is available via https:\/\/github.com\/joachimwolff\/sparse-neighbors-search and as a conda package via the bioconda channel.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab394","type":"journal-article","created":{"date-parts":[[2021,5,19]],"date-time":"2021-05-19T19:36:11Z","timestamp":1621452971000},"page":"4006-4013","source":"Crossref","is-referenced-by-count":17,"title":["Robust and efficient single-cell Hi-C clustering with approximate k-nearest neighbor graphs"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9985-955X","authenticated-orcid":false,"given":"Joachim","family":"Wolff","sequence":"first","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, University of Freiburg , 79110 Freiburg, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8231-3323","authenticated-orcid":false,"given":"Rolf","family":"Backofen","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, University of Freiburg , 79110 Freiburg, Germany"},{"name":"Signalling Research Centre CIBSS, University of Freiburg , 79104 Freiburg, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3079-6586","authenticated-orcid":false,"given":"Bj\u00f6rn","family":"Gr\u00fcning","sequence":"additional","affiliation":[{"name":"Bioinformatics Group, Department of Computer Science, University of Freiburg , 79110 Freiburg, Germany"}]}],"member":"286","published-online":{"date-parts":[[2021,5,22]]},"reference":[{"key":"2023051607082352300_btab394-B1","first-page":"420","volume-title":"International Conference on Database Theory","author":"Aggarwal","year":"2001"},{"key":"2023051607082352300_btab394-B2","volume-title":"Adaptive Control Processes: A Guided Tour","author":"Bellman","year":"2015"},{"key":"2023051607082352300_btab394-B3","author":"Beyer","year":"1999"},{"key":"2023051607082352300_btab394-B4","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1038\/nrg.2016.112","article-title":"Organization and function of the 3d genome","volume":"17","author":"Bonev","year":"2016","journal-title":"Nat. Rev. Genet"},{"key":"2023051607082352300_btab394-B5","first-page":"21","author":"Broder","year":"1997"},{"key":"2023051607082352300_btab394-B6","first-page":"545","volume-title":"Curse of Dimensionality","author":"Chen","year":"2009"},{"key":"2023051607082352300_btab394-B7","first-page":"800","volume-title":"International Conference on Intelligent Data Engineering and Automated Learning","author":"Deegalla","year":"2007"},{"key":"2023051607082352300_btab394-B8","doi-asserted-by":"crossref","first-page":"1306","DOI":"10.1126\/science.1067799","article-title":"Capturing chromosome conformation","volume":"295","author":"Dekker","year":"2002","journal-title":"Science"},{"key":"2023051607082352300_btab394-B9","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-019-12235-0","article-title":"Functional interpretation of single cell similarity maps","volume":"10","author":"DeTomaso","year":"2019","journal-title":"Nat. Commun"},{"key":"2023051607082352300_btab394-B10","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1101\/gr.5571506","article-title":"Chromosome conformation capture carbon copy (5c): a massively parallel solution for mapping interactions between genomic elements","volume":"16","author":"Dostie","year":"2006","journal-title":"Genome Res"},{"key":"2023051607082352300_btab394-B11","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1038\/nature21711","article-title":"Single-nucleus hi-C reveals unique chromatin reorganization at oocyte-to-zygote transition","volume":"544","author":"Flyamer","year":"2017","journal-title":"Nature"},{"key":"2023051607082352300_btab394-B12","doi-asserted-by":"crossref","first-page":"3600","DOI":"10.15252\/embj.201798083","article-title":"A mechanism of cohesin-dependent loop extrusion organizes zygotic genome architecture","volume":"36","author":"Gassler","year":"2017","journal-title":"EMBO J"},{"key":"2023051607082352300_btab394-B13","author":"Hammer","year":"1962"},{"key":"2023051607082352300_btab394-B14","doi-asserted-by":"crossref","first-page":"i224","DOI":"10.1093\/bioinformatics\/bts224","article-title":"Graphclust: alignment-free structural clustering of local rna secondary structures","volume":"28","author":"Heyne","year":"2012","journal-title":"Bioinformatics"},{"key":"2023051607082352300_btab394-B15","first-page":"506","author":"Hinneburg","year":"2000"},{"key":"2023051607082352300_btab394-B16","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1007\/978-3-642-13818-8_34","volume-title":"International Conference on Scientific and Statistical Database Management","author":"Houle","year":"2010"},{"key":"2023051607082352300_btab394-B17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1038\/s41576-019-0195-2","article-title":"Methods for mapping 3d chromosome architecture","volume":"21","author":"Kempfer","year":"2020","journal-title":"Nat. Rev. Genet"},{"key":"2023051607082352300_btab394-B18","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1093\/comjnl\/9.1.60","article-title":"Computer programs for hierarchical polythetic classification (\u201cSimilarity Analyses\u201d)","volume":"9","author":"Lance","year":"1966","journal-title":"Comput. J"},{"key":"2023051607082352300_btab394-B19","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/978-3-540-72031-7_16","volume-title":"International Symposium on Bioinformatics Research and Applications","author":"Lee","year":"2007"},{"key":"2023051607082352300_btab394-B20","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1126\/science.1181369","article-title":"Comprehensive mapping of long-range interactions reveals folding principles of the human genome","volume":"326","author":"Lieberman-Aiden","year":"2009","journal-title":"Science"},{"key":"2023051607082352300_btab394-B21","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1016\/j.molcel.2019.12.021","article-title":"Chromosome conformation capture and beyond: toward an integrative view of chromosome structure and function","volume":"77","author":"McCord","year":"2020","journal-title":"Mol. Cell"},{"key":"2023051607082352300_btab394-B22","author":"McInnes","year":"2020"},{"key":"2023051607082352300_btab394-B23","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1038\/nature12593","article-title":"Single-cell hi-c reveals cell-to-cell variability in chromosome structure","volume":"502","author":"Nagano","year":"2013","journal-title":"Nature"},{"key":"2023051607082352300_btab394-B24","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1038\/nature23001","article-title":"Cell-cycle dynamics of chromosomal organization at single-cell resolution","volume":"547","author":"Nagano","year":"2017","journal-title":"Nature"},{"key":"2023051607082352300_btab394-B25","first-page":"2825","article-title":"Scikit-learn: machine learning in Python","volume":"12","author":"Pedregosa","year":"2011","journal-title":"J. Mach. Learn. Res"},{"key":"2023051607082352300_btab394-B26","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1038\/nmeth.4155","article-title":"Massively multiplex single-cell hi-c","volume":"14","author":"Ramani","year":"2017","journal-title":"Nat. Methods"},{"key":"2023051607082352300_btab394-B27","doi-asserted-by":"crossref","first-page":"1348","DOI":"10.1038\/ng1896","article-title":"Nuclear organization of active and inactive chromatin domains uncovered by chromosome conformation capture\u2013on-chip (4c)","volume":"38","author":"Simonis","year":"2006","journal-title":"Nat. Genet"},{"key":"2023051607082352300_btab394-B28","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1038\/nature21429","article-title":"3d structures of individual mammalian genomes studied by single-cell hi-c","volume":"544","author":"Stevens","year":"2017","journal-title":"Nature"},{"key":"2023051607082352300_btab394-B29","doi-asserted-by":"crossref","first-page":"W177","DOI":"10.1093\/nar\/gkaa220","article-title":"Galaxy HiCExplorer 3: a web server for reproducible Hi-C, capture Hi-C and single-cell Hi-C data analysis, quality control and visualization","volume":"48","author":"Wolff","year":"2020","journal-title":"Nucleic Acids Res"},{"key":"2023051607082352300_btab394-B30","first-page":"btaa924","article-title":"Scool: a new data storage format for single-cell Hi-C data","author":"Wolff","year":"2020","journal-title":"Bioinformatics"},{"key":"2023051607082352300_btab394-B31","doi-asserted-by":"crossref","first-page":"1341","DOI":"10.1038\/ng1891","article-title":"Circular chromosome conformation capture (4c) uncovers extensive networks of epigenetically regulated intra- and interchromosomal interactions","volume":"38","author":"Zhao","year":"2006","journal-title":"Nat. Genet"},{"key":"2023051607082352300_btab394-B32","doi-asserted-by":"crossref","first-page":"14011","DOI":"10.1073\/pnas.1901423116","article-title":"Robust single-cell hi-c clustering by convolution-and random-walk\u2013based imputation","volume":"116","author":"Zhou","year":"2019","journal-title":"Proc. Natl. Acad. Sci. USA"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab394\/39310136\/btab394.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/22\/4006\/50335080\/btab394.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/22\/4006\/50335080\/btab394.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T07:10:40Z","timestamp":1684221040000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/22\/4006\/6281072"}},"subtitle":[],"editor":[{"given":"Pier Luigi","family":"Martelli","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,5,22]]},"references-count":32,"journal-issue":{"issue":"22","published-print":{"date-parts":[[2021,11,18]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab394","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,11,15]]},"published":{"date-parts":[[2021,5,22]]}}}