Sage Journals: Discover world-class research

Abstract

High-throughput chromosome conformation capture (Hi-C) technology captures spatial interactions of DNA sequences into matrices, and software tools are developed to identify topologically associating domains (TADs) from the Hi-C matrices. With structural information theory, SuperTAD adopted a dynamic programming approach to find the TAD hierarchy with minimal structural entropy. However, the algorithm suffers from high time complexity. To accelerate this algorithm, we design and implement an approximation algorithm with a theoretical performance guarantee. We implemented a package, SuperTAD-Fast. Using Hi-C matrices and simulated data, we demonstrated that SuperTAD-Fast achieved great runtime improvement compared with SuperTAD. SuperTAD-Fast shows high consistency and significant enrichment of structural proteins from Hi-C data of human cell lines in comparison with the existing six hierarchical TADs detecting methods.

Get full access to this article

View all access options for this article.

References

Cresswell

, Stansfield

, Dozmorov

. SpectralTAD: An r package for defining a hierarchy of topologically associated domains using spectral clustering. BMC Bioinformatics, 2020; 21(1):319; doi: 10.1186/s12859-020-03652-w

Dali

, Blanchette

. A critical assessment of topologically associating domain prediction tools. Nucleic Acids Res, 2017; 45(6):2994–3005; doi: 10.1093/nar/gkx145

Dixon

, Gorkin

, Ren

. Chromatin domains: The unit of chromosome organization. Mol Cell, 2016; 62(5):668–680; doi: 10.1016/j.molcel.2016.05.018

Dostie

, Richmond

, Arnaout

, et al. Chromosome Conformation Capture Carbon Copy (5C): A massively parallel solution for mapping interactions between genomic elements. Genome Res, 2006; 16(10):1299–1309; doi: 10.1101/gr.5571506

, Li

, Ding

, et al. The hierarchical folding dynamics of topologically associating domains are closely related to transcriptional abnormalities in cancers. Comput Struct Biotechnol J, 2021; 19:1684–1693; doi: 10.1016/j.csbj.2021.03.018

Durand

, Shamim

, Machol

, et al. Juicer Provides a One-Click System for Analyzing Loop-Resolution Hi-C Experiments. Cell Syst, 2016; 3(1):95–98; doi: 10.1016/j.cels.2016.07.002

Ghavi-Helm

, Jankowski

, Meiers

, et al. Highly rearranged chromosomes reveal uncoupling between genome topology and gene expression. Nat Genet, 2019; 51(8):1272–1282; doi: 10.1038/s41588-019-0462-3

Haddad

, Vaillant

, Jost

. IC-Finder: Inferring robustly the hierarchical organization of chromatin folding. Nucleic Acids Res, 2017; 45(10):e81; doi: 10.1093/nar/gkx036

Kim

, Yu

, Kaang

. CTCF as a multifunctional protein in genome regulation and gene expression. Exp Mol Med, 2015; 47(6):e166–e166; doi: 10.1038/emm.2015.33

10.

Kurgan

, Cios

. CAIM discretization algorithm. IEEE Trans Knowl Data Eng, 2004; 16(2):145–153; doi: 10.1109/tkde.2004.1269594

11.

, Yin

, Xu

, et al. Decoding topologically associating domains with ultra-low resolution Hi-C data by graph structural entropy. Nat Commun, 2018; 9(1):3265.

12.

Lieberman-Aiden

, van Berkum

, Williams

, et al. Comprehensive mapping of long-range interactions reveals folding principles of the human genome. Science, 2009; 326(5950):289–293; doi: 10.1126/science.1181369

13.

Lupianez

, Kraft

, Heinrich

, et al. Disruptions of topological chromatin domains cause pathogenic rewiring of gene-enhancer interactions. Cell, 2015; 161(5):1012–1025; doi: 10.1016/j.cell.2015.04.004

14.

Norton

, Emerson

, Huang

, et al. Detecting hierarchical genome folding with network modularity. Nat Methods, 2018; 15(2):119–122; doi: 10.1038/nmeth.4560

15.

Phillips-Cremins

, Sauria

, Sanyal

, et al. Architectural protein subclasses shape 3D organization of genomes during lineage commitment. Cell, 2013; 153(6):1281–1295; doi: 10.1016/j.cell.2013.04.053

16.

Rao

, Huntley

, Durand

, et al. A 3D map of the human genome at kilobase resolution reveals principles of chromatin looping. Cell, 2014; 159(7):1665–1680; doi: 10.1016/j.cell.2014.11.021

17.

Sefer

. A comparison of topologically associating domain callers over mammals at high resolution. BMC Bioinformatics, 2022; 23(1):127; doi: 10.1186/s12859-022-04674-2

18.

Tang

, Ji

, Fang

, et al. Discretization-strategy-based solution for berth allocation and quay crane assignment problem. Jmse, 2022; 10(4):495; doi: 10.3390/jmse10040495

19.

Van

, Furlong

. The role of transcription in shaping the spatial organization of the genome. Nat Rev Mol Cell Biol, 2019; 20(6):327–337; doi: 10.1038/s41580-019-0114-6

20.

, He

, Tan

. Identifying topologically associating domains and subdomains by Gaussian mixture model and proportion test. Nat Commun, 2017; 8(1):535; doi: 10.1038/s41467-017-00478-8

21.

Zhan

, Mariani

, Barozzi

, et al. Reciprocal insulation analysis of Hi-C data shows that TADs represent a functionally but not structurally privileged scale in the hierarchical folding of chromosomes. Genome Res, 2017; 27(3):479–490; doi: 10.1101/gr.212803.116

22.

Zhang

, Wang

, Li

. SuperTAD: Robust detection of hierarchical topologically associated domains with optimized structural information. Genome Biol, 2021; 22(1):45; doi: 10.1186/s13059-020-02234-6

23.

Zufferey

, Tavernari

, Oricchio

, et al. Comparison of computational methods for the identification of topologically associating domains. Genome Biol, 2018; 19(1):217; doi: 10.1186/s13059-018-1596-9

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

0.30 MB

SuperTAD-Fast: Accelerating Topologically Associating Domains Detection Through Discretization

Abstract

Get full access to this article

References

Supplementary Material