Topologically associating domains (TADs) are the most fundamental elements and significant structures of the eukaryotic genome. Currently, algorithms have been developed to find the TADs. But few algorithms are reported to compare the similarity of TADs between genomes. In this study, mice Hi-C sequencing data of four contrasts were enrolled. Seventeen algorithms, including BPscore, Jaccard index (JI) distance, VI distance, image hash, image subtraction, image variance, and so on, were used to quantify the genomic similarity of TADs. Image subtraction, Euclidean distance, and Manhattan distance were significantly better for TAD difference detection than the others. Deferent Hash (dHash) with the best zoom size ranked the second, followed by improved Hamming distance algorithm and JI distance. Advantages and disadvantages of various algorithms for quantifying the similarity of TADs were compared. Our work could provide the fundament for TADs comparison.
Get full access to this article
View all access options for this article.
References
1.
BayH., TuytelaarsT., and Van GoolL.2006. Surf: Speeded up robust features. European Conference on Computer Vision. 3951, 405–417.
2.
BirchfieldS., and TomasiC.1999. Depth discontinuities by pixel-to-pixel stereo computer. Int. J. Comput. Vision, 3, 269–293.
3.
ChaitB.T.2011. Mass spectrometry in the postgenomic era. J. Annu. Rev. Biochem. 80, 239–246.
4.
DekkerJ., RippeK., DekkerM., et al.2002. Capturing chromosome conformation. J. Sci. 295, 1306–1311.
5.
DixonJ.R., SelvarajS., YueF., et al.2012. Topological domains in mammalian genomes identified by analysis of chromatin interactions. J. Nat. 485, 376–380.
6.
DostieJ., RichmondT.A., ArnaoutR.A., et al.2006. Chromosome Conformation Capture Carbon Copy (5C): A massively parallel solution for mapping interactions between genomic elements. J. Genome Res. 16, 1299–1309.
7.
DurandN.C., RobinsonJ.T., ShamimM.S., et al.2016. Juicebox provides a visualization system for Hi-C contact maps with unlimited zoom. J. Cell Syst. 3, 99–101.
8.
FangpingZ.2012. Depth Information Extraction Based On Binocular Stereo Vision System. Beijing Jiaotong University, Beijing.
9.
FilippovaD., PatroR., DuggalG., et al.2014. Identification of alternative topological domains in chromatin. J. Algorithms Mol. Biol. 9, 14.
10.
FrankeM., IbrahimD.M., AndreyG., et al.2016. Formation of new chromatin domains determines pathogenicity of genomic duplications. J. Nat. 538, 265–269.
11.
HaitianZ.2015. Research on Stereo Matching Algorithm in Stereo Vision Ranging. Xidian University, Xi'an.
12.
JiahengH., XiaoweiL., BenhuiC., et al.2017. A comparative study of image similarity algorithms based on Hash. J. Dali Univ. 2, 32–37.
13.
JiaweiL., ZhiqiangY., and ShuyanL.2011. Novel method for phylogenetic tree construction based on Novel method for phylogenetic tree construction based on correlation feature and fuzzy clustering. J. Appl. Res. Comput. 28, 2844–2847.
14.
KaurB., KaurG., and KaurA.2014. Detection and classification of printed circuit board defects using image subtraction method. IEEE, Chandigarh, India. pp. 1–5.
15.
Lieberman-AidenE., van BerkumN. L., WilliamsL., et al.2009. Comprehensive mapping of long-range interactions reveals folding principles of the human genome. J. Sci. 326, 289–293.
16.
LoweD.G.2004. Distinctive image features from scale-invariant key point. Int. J. Comput. 60, 91–110.
17.
LupianezD.G., KraftK., HeinrichV., et al.2015. Disruptions of topological chromatin domains cause pathogenic rewiring of gene-enhancer interactions. J. Cell, 161, 1012–1025.
18.
PopeB.D., RybaT., DileepV., et al.2014. Topologically associating domains are stable units of replication-timing regulation. J. Nat. 515, 402–405.
19.
QiongyangW., and LifangH.2018. On the average hamming distance and mean square deviation for binary superimpose code δ(n,d,k). J. Math. Pract. Theory, 48, 251–255.
20.
RaoS.S., HuntleyM.H., DurandN.C., et al.2014. A 3D map of the human genome at kilobase resolution reveals principles of chromatin looping. J. Cell, 159, 1665–1680.
21.
RiscaV.I., and GreenleafW.J.2015. Unraveling the 3D genome: Genomics tools for multiscale exploration. J. Trends Genet. 31, 357–372.
22.
SauerwaldN., and KingsfordC.2018. Quantifying the similarity of topological domains across normal and cancer human cell types. J. Bioinformatics, 34, i475–i483.
23.
SchmittA.D., HuM., and RenB.2016. Genome-wide mapping and analysis of chromosome architecture. J. Nat. Rev. Mol. Cell Biol. 17, 743–755.
24.
SerraF., BauD., GoodstadtM., et al.2017. Automatic analysis and 3D-modelling of Hi-C data using TADbit reveals structural features of the fly chromatin colors. J. PLoS Comput. Biol. 13, e1005665.
25.
ServantN., LajoieB.R., NoraE.P., et al.2012. HiTC: Exploration of high-throughput ‘C’ experiments. J. Bioinformatics, 28, 2843–2844.
26.
ServantN., VaroquauxN., LajoieB.R., et al.2015. HiC-Pro: An optimized and flexible pipeline for Hi-C data processing. J. Genome Biol. 16, 259.
27.
ShenQ., ZhiminL., and NanZ.2017. Improved particle swarm optimization algorithm based on Improved particle swarm optimization algorithm based on Hamming distance for traveling salesman problem. J. Comput. Appl. 37, 2767–2772.
28.
SimonisM., KlousP., SplinterE.et al.2006. Nuclear organization of active and inactive chromatin domains uncovered by chromosome conformation capture-on-chip (4C). J. Nat. Genet. 38, 1348–1354.
29.
ValtonA.L., and DekkerJ.2016. TAD disruption as oncogenic driver. J. Curr. Opin. Genet. Dev. 36, 34–40.
30.
WangQ., SunQ., CzajkowskyD.M., et al.2018. Sub-kb Hi-C in D. melanogaster reveals conserved characteristics of TADs between insect and mammalian cells. J. Nat. Commun. 9, 188.
31.
WeinrebC., and RaphaelB.J.2016. Identification of hierarchical chromatin domains. J. Bioinformatics, 32, 1601–1609.
32.
WuP., LiT., LiR., et al.2017. 3D genome of multiple myeloma reveals spatial genome disorganization associated with copy number variations. J. Nat. Commun. 8, 1937.
33.
XianglinZ., HuanF., and XiaowoW.2018. Progress in three-dimensional Genome data Analysis. J. Prog. Biochem. Biophys. 45, 1093–1105.
34.
XiaogangY., FeiC., DongM., et al.2005. Study on the image grayscale matching algorithm based on similarity measures. J. Syst. Eng. Electr. 27, 305–314.
35.
YuM., and RenB.2017. The Three-Dimensional Organization of Mammalian Genomes. J. Annu. Rev. Cell Dev. Biol. 33, 265–289.
36.
YuboZ.2018. Three-dimensional genomics and precise biology. J. Chin. Biochem. Mol. Biol. 34, 351–363.
37.
YumeiY., YiP., and JunhuiQ.2019. Research on image similarity retrieval algorithm based on color variance. J. Commun. Technol. 52, 74–79.
38.
ZaborowskiR., and WilczynskiB.2019. BPscore: an effective metric for meaningful comparisons of structural chromosome segmentations. J. Comput. Biol. 26.
39.
ZhaoZ., TavoosidanaG., SjolinderM., et al.2006. Circular chromosome conformation capture (4C) uncovers extensive networks of epigenetically regulated intra- and interchromosomal interactions. J. Nat. Genet. 38, 1341–1347.
40.
ZuffereyM., TavernariD., OricchioE., et al.2018. Comparison of computational methods for the identification of topologically associating domains. J. Genome Biol. 19, 217.
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.
