A Review of Methods to Quantify the Genomic Similarity of Topological Associating Domains

Abstract

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.

1. Introduction

With the rise of three-dimensional (3D) genomics, many techniques have been proposed and applied to the study of 3D structure of chromosomes. In 2002, capturing chromosome conformation (3C) (Dekker et al., 2002) was used to determine the chromatin interaction between specific point to point. In 2006, chromosome conformation capture-on-chip (4C) (Simonis et al., 2006; Zhao et al., 2006) technique was developed to determine chromatin interactions from a single point to multipoint. And chromosome conformation capture carbon copy (5C) (Dostie et al., 2006) technique was used to measure chromatin interactions between multiple and multiple points in 2006. Based on 3C technology, Hi-C (Lieberman-Aiden et al., 2009) technology was developed in 2009. The remote interaction of chromatin and the regulatory relationship between the 3D spatial structure of genome and possible genes can be revealed by Hi-C. Hi-C technology discovered the interaction between genes and transcriptional regulatory elements in the whole genome with “multiple to multiple” patterns (Yubo, 2018). The interaction pattern of all DNA elements in chromatin was analyzed, and the 3D spatial structure (Lieberman-Aiden et al., 2009) of genome was constructed with Hi-C. It has become a typical representative of 3D genomics technology.

The 3D structure of eukaryotic genome is complex. In the nucleus, DNA contains one or more genes, and regulatory elements can be spaced apart to form topologically associating domains (TADs) (Chait, 2011). An open or a closed area of chromatin structure alternately forms A or B compartment associated with function, respectively (Lieberman-Aiden et al., 2009; Chait, 2011). As a result of random collisions, two remote gene loci will be identified to each other at higher frequencies. The loop spatial conformation of remote transcriptional regulation and the complex network structure was observed (Risca and Greenleaf, 2015; Schmitt et al., 2016).

As the most fundamental and important elements of eukaryotic genome structure (Wang et al., 2018), the TADs were first defined in 2012 (Dixon et al., 2012). The cooperative relationship between the region and structural protein factor CTCF (CCCTC-Binding factor) was further identified (Dixon et al., 2012). In 2017 the concept of chromatin loops was proposed, which was considered as the smallest unit of genetic regulation (Yu and Ren, 2017). 3D genome of multiple myeloma revealed spatial genome disorganization associated with copy number variations by Wu et al. (2017). TADs were found to be conserved between insect and mammalian by Wang et al. in 2018 (Wang et al., 2018).

The important progress of TAD research can't be separated from the development of related algorithms. DomainCaller (Dixon et al., 2012) based on Hidden Markov (HHM) was the first developed algorithm for TAD calling, which was put forward by Dixon et al. Arrowhead (Rao et al., 2014; Durand et al., 2016), Armatus (Filippova et al., 2014), TADtree (Weinreb and Raphael, 2016), TADbit (Serra et al., 2017), and other algorithms were proposed shortly. However, few algorithms were developed for TAD similarity quantization. Among them, Jaccard index (JI) distance (Dixon et al., 2012) and information entropy (VI distance) (Filippova et al., 2014) were classical algorithms. The JI was mainly to quantify the similarity of the TADs by comparing the degree of overlap of the TAD boundaries. And the information entropy mainly measured the variation between the information. However, the new algorithms for comparing TAD similarity were not proposed until 2018. BPscore (Zaborowski and Wilczynski, 2019) was put forward for meaningful comparisons of structural chromosome segmentations. An algorithm for quantifying the similarity of topological domains across normal and cancer human cell types was also proposed by Sauerwald and Kingsford (2018).

Although some algorithms were developed to compare the similarity of TADs, comparison between these algorithms has not been reported, hitherto. Therefore, the existing TAD similarity quantization algorithms and improved algorithms based on the existing algorithms were compared in this study. These days TADs could be visualized. Therefore, various algorithms were compared from the point of image similarity. This study is the first systematic research to compare different algorithms for quantifying the similarity of TADs.

2. Methods

2.1. Data

Four sets of publicly released Hi-C data from GEO (Gene Expression Omnibus, GSM862720, GSM862721, GSM862722, GSM892304) were downloaded as test data in this study (Dixon et al., 2012). According to the differences in the experimental operation, the four samples downloaded from GEO were combined into four groups. They were identical sample pairs, biological duplicate sample pairs, different endonuclease sample pairs, and different cell line sample pairs, as summarized in Table 1. Hi-C Pro (version 2.10.0) (Servant et al., 2015) pipeline was used to generate Hi-C maps at 40 kb resolution. Default parameters were used. DomainCaller (Dixon et al., 2012) was used to identify TADs. All TADs were visualized with R package HiTC (Servant et al., 2012).

Table 1.

Hi-C Sample Pairs Used for Analysis

Group	Characteristic	GEO no.	Species	Cell lines	Enzyme	Platform
A	Identical sample	GSM862720	Mouse ES	mESC line J1	HindIII	Illumina HiSeq 2000
A	Identical sample	GSM862720	Mouse ES	mESC line J1	HindIII	Illumina HiSeq 2000
B	Replicate	GSM862720	Mouse ES	mESC line J1	HindIII	Illumina HiSeq 2000
B	Replicate	GSM862721	Mouse ES	mESC line J1	HindIII	Illumina HiSeq 2000
C	Enzyme difference	GSM862720	Mouse ES	mESC line J1	HindIII	Illumina HiSeq 2000
C	Enzyme difference	GSM862722	Mouse ES	mESC line J1	Ncol	Illumina HiSeq 2000
D	Cell line difference	GSM862720	Mouse ES	mESC line J1	HindIII	Illumina HiSeq 2000
D	Cell line difference	GSM892304	Mouse ES	cortex	HindIII	Illumina HiSeq 2000

2.2. Overview of the methods

Seventeen algorithms were used to quantify the similarity of TADs, as summarized in Table 2. Details of various algorithms can be found in the Supplementary Data. Seventeen algorithms were divided into four categories according to their properties. The first was classic algorithms used widely and reported repeatedly, mainly including BPscore, JI distance, and VI distance. Sequence-based statistical algorithms were second quantized similarity from the distance between sequences, which were improved based on BPscore. The third category contained image hash algorithms, followed by image statistical algorithms quantifying TAD similarity from image subtraction, variance, various distance, and similarity. All the algorithms were implemented by Python 3.5.

Table 2.

Methods to Quantify the Similarity of Topological Domains Used in This Comparison

	Category	Method	Availability/formula
Sequence-based algorithms	Classic algorithms	BP distance (Zaborowski and Wilczynski, 2019)	DOI:10.1089/cmb.2018.0162
		BP distance (Zaborowski and Wilczynski, 2019)	www.almob.org/content/9/1/14
		VI distance (Filippova et al., 2014)	https://www-nature-com-s.web.bisu.edu.cn/articles/nature11082
		JI distance (Dixon et al., 2012)
	Sequence-based statistical algorithms	Euclidean distance (Lowe, 2004; Bay et al., 2006; )	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ED ( a , b ) }} = \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 1}^m \sqrt { \left( {{a_{ij}}} \right. - {{ \left. {{b_{ij}}} \right) }^2}}$$ \end{document}
		Hamming distance (Shen et al., 2017; Qiongyang and Lifang, 2018)	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{HD ( a , b ) }} = \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 1}^m dH \left( {{a_{ij}}} \right. , \left. {{b_{ij}}} \right)$$ \end{document}
		Chebyshev distance (Jiawei et al., 2011)	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{CD ( a , b ) }} = { \rm{max}}_{ij = 1}^{nm} \left\vert {{a_{ij}} - {b_{ij}}} \right\vert$$ \end{document}
Image-based algorithms	Image hash algorithms	aHash (Jiaheng et al., 2017)	Supplementary note 1
		pHash (Jiaheng et al., 2017)	Supplementary note 1
		dHash (Jiaheng et al., 2017)	Supplementary note 1
	Image statistical algorithms	Image subtraction (Kaur et al., 2014)	Supplementary note 1
		Image variance (Yumei et al. 2019)	Supplementary note 1
		Euclidean distance	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{ED ( a , b ) }} = \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 1}^m \sqrt { \left( {{a_{ij}}} \right. - {{ \left. {{b_{ij}}} \right) }^2}}$$ \end{document}
		Manhattan distance (Birchfield and Tomasi, 1999; Haitian, 2015)	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \rm{MD ( a , b ) }} = \mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = 1}^m \left\vert {{a_{ij}} - {b_{ij}}} \right\vert$$ \end{document}
		Jaccard similarity (Dixon et al., 2012)	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ { \rm { JI - Sim ( a , b ) \; } } = { \frac { \left\vert { a \cap b } \right\vert } { \left\vert { a \cup b } \right\vert } } = { \frac { \left\vert { a \cap b } \right\vert } { \left\vert a \right\vert + \left\vert b \right\vert - \left\vert { a \cap b } \right\vert } } $$ \end{document}
		Hamming similarity	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ { \rm { HM - Sim \; = \; } } { \frac { 1 - \mathop \sum \nolimits_ { i = 1 } ^n \mathop \sum \nolimits_ { j = 1 } ^m dH \left( { { a_ { ij } } } \right. , \left. { { b_ { ij } } } \right) } { n \times m } } $$ \end{document}
		Pearson correlation (Fangping, 2012)	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ { \rm { Corr ( a , b ) } } \; = \; { \frac { \mathop \sum \nolimits_ { i , j = 1 , 1 } ^ { n , m } \left( { { a_ { ij } } - \bar a } \right) \left( { { b_ { ij } } - \bar b } \right) } { \sqrt { \mathop \sum \nolimits_ { i , j = 1 , 1 } ^ { n , m } \left( { { a_ { ij } } } \right. - { { \left. { \bar a } \right) } ^2 } } { \rm { \; } } \sqrt { \mathop \sum \nolimits_ { i , j = 1 , 1 } ^ { n , m } \left( { { b_ { ij } } } \right. - { { \left. { \bar b } \right) } ^2 } } } } $$ \end{document}
		Cosine similarity (Xiaogang et al., 2005)	\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$ { \rm { CosSim ( a , b ) \; = } } { \frac { \mathop \sum \nolimits_ { i , j = 1 , 1 } ^ { n , m } { a_ { ij } } { b_ { ij } } } { \sqrt { \mathop \sum \nolimits_ { i , j } ^ { n , m } { a_ { ij } } ^2 } \sqrt { \mathop \sum \nolimits_ { i , j } ^ { n , m } { b_ { ij } } ^2 } } } $$ \end{document}

Theoretically, the similarity of TADs was supposed to decrease step by step from the first sample pair to the fourth sample pair, while the distance and variance were supposed to increase gradually. This was also a criterion to evaluate the performance of the algorithms to quantify TAD similarity. So the consistence of the various algorithms, which equaled to the total number of data that the similarity of TADs was decreasing or distance was increasing step by step from the first sample pairs to the fourth sample pairs divide by the total number of the data, was calculated to evaluate their merits and demerits.

2.3. Findings

2.3.1. The results of classic algorithms

Three classic algorithms were compared in the first category, including BP distance, VI distance based on information entropy, and JI distance based on the JI, respectively. Three algorithms were applied to quantify four groups of TADs set in Table 2. In theory, from group 1 to group 4, the distance between groups increased in turn. The results of BP distance algorithm revealed that only 7 of the 19 chromosomes illustrated incremental trend from group 1 to group 4 (Fig. 1a). Similarly, VI distance results showed an increasing trend of eight chromosomes from group 1 to group 4 (Fig. 1a). JI distance was one of the most widely used methods to quantify the similarity of TADs, which performed superior. Of the 19 chromosomes, 14 showed an increasing trend from group 1 to group 4 (Fig. 1a). The consistence rate of JI distance is 73.68% (Fig. 6a). Trend of these three algorithms was visualized. In terms of the overall data density distribution, BP distance and VI distance were not as effective as JI distance in differentiating TAD pairs with smaller differences. The distribution of VI and BP was similar, in contrast to JI. On the whole, only JI distance displayed an obvious increasing trend from group A to group D among the three algorithms (Fig. 1b). These results suggested that JI distance excelled BP distance and VI distance in quantifying TAD similarity among the three classic algorithms.

FIG. 1.

The results of classic algorithms. (a) The heatmap of category I in four groups. (b) The data distribution of the three algorithms in the four groups.

2.3.2. The results of sequence-based statistical algorithms

The highest consistence rate of the three algorithms provided by classic algorithms was only 73.68%. A method to normalize two TAD sets of different lengths to the same length was provided by BPscore. Therefore, improved algorithms based on BPscore were proposed. In this part, hamming distance, Euclidean distance, and Chebyshev distance were applied to quantify the similarity of TAD set, respectively. The results of hamming distance were the most satisfactory. Sixteen out of the 19 chromosomes presented an increasing trend from group 1 to group 4 (Fig. 2a). The consistence rate reached 84.21% (Fig. 6a), which was 10.53% higher than JI distance. Euclidean distance and Chebyshev distance did marginally worse. Only eight chromosomes from group 1 to group 4 displayed a raise tendency (Supplementary Fig. S1a). The same conclusion can be drawn from the distribution data of various algorithms in different groups (Fig. 2b). In summary, hamming distance was better than Euclidean distance, Chebyshev distance in quantifying the genomic similarity of TADs.

FIG. 2.

The results of sequence-based statistical algorithms. (a) The heatmap of hamming distance in four groups. (b) The data distribution of the Hamming distance, Euclidean distance, and Chebyshev distance.

2.3.3. The results of image hash algorithms

In this part, the four groups of TAD dataset in Table 2 were visualized. A TAD image can be generated from each chromosome. The mouse genome consists of 19 chromosomes except sex chromosomes. Therefore, 76 pairs of TAD images were generated from 4 groups. Then OpenCV 4.0.1 of Python 3.5 was used to scale and grayscale the image. For each pair of images, Average Hash (aHash), Deferent Hash (dHash), and Perceptual Hash (pHash) algorithms were used to test similarity of each pair. The images were scaled to nine different zoom sizes, when testing the three image hash algorithms. The resolutions of 8 × 8, 16 × 16, 32 × 32, 64 × 64, 128 × 128, 256 × 256, 480 × 480 (original size), 512 × 512, and 1024 × 1024 were enrolled, respectively.

The consistence rate of the three algorithms was less than 15% when the image was scaled to 8 × 8. Only three chromosomes showed an increasing trend from group 1 to group 4 in dHash. As the size of the scale rose, the information of the image retained increased (Supplementary Fig. S1b–d). Thus, the similarity tendency and consistence were promoted gradually. 128 × 128 was the best zoom size for aHash with 14 chromosomes showing consistence trend (Fig. 3a). 512 × 512 was the best zoom size for dHash with 18 chromosomes showing consistence trend, as well as 256 × 256. And the best zoom size of pHash was 512 × 512 with nine chromosomes showing consistence trend (Fig. 3b). The consistence trend was decreasing when zoom size was amplified to 1024 × 1024 (Fig. 3a). These results illustrated that the more details of each group of images were retained, the more the similarity of TAD images can be quantified. In conclusion, 512 × 512 was the best zoom size for TAD images. The consistence rate of aHash, dHash, and pHash was 68.42%, 94.74%, and 47.37%, respectively (Fig. 3b). aHash and dHash were superior to pHash in distinguishing images (Fig. 3c).

FIG. 3.

The results of image hash algorithms. (a) The chromosome counts of three hash algorithms showed consistence trend with the nine different zoom dimensions. (b) The heatmap of three hash algorithms with the best zoom dimension (512 × 512). (c) The data distribution of three hash algorithms with the best zoom dimension (512 × 512).

2.3.4. The results of image statistical algorithms

In this part, the four groups of TAD dataset in Table 2 also were visualized. Then these images were grayed by OpenCV 4.0.1 of Python 3.5. Then image statistical algorithms were applied to quantify the similarity of TADs.

The differences and similarities were reflected by differentiating all corresponding pixels for each pair of images, which was defined as image subtraction. Variance recorded the main information of the image. Fluctuation of pixel features can be impactfully reflected by variance. Therefore, image subtraction and image variance were applied to quantify TAD similarity.

Image subtraction was a unique choice for the similarity comparison of TAD images from the test results (Fig. 4a). The consistence of the algorithm reached 100% (Fig. 6a). Only 6 of the 19 chromosomes revealed a rising trend from group 1 to group 4 using image variance method (Fig. 4a), and the consistence was only 31.58% (Fig. 6a). From the view of the whole data distribution, the results of image subtraction were more concentrated. The results of image variance method were scattered. And the data of group B and group C fluctuated greatly (Fig. 4b). Compared with the method of image variance, image subtraction bettered.

FIG. 4.

The results of image subtraction and image variance. (a) The heatmap of image subtraction and image variance. (b) The data distribution of image subtraction and image variance.

Two kinds of distances and four kinds of similarity were primarily selected to quantify the similarity of TAD images from the view of statistical algorithms. The results revealed that the Euclidean distance and the Manhattan distance were better. There were 19 chromosomes from group 1 to group 4 that exhibited a rising trend in turn (Fig. 5a). The consistence of these algorithms was 100% (Fig. 6a). The overall data distribution also revealed the same conclusion (Fig. 5b). However, the performance of Chebyshev distance, hamming distance, Jaccard similarity, Pearson correlation coefficient, and cosine similarity was not as good as Euclidean distance and the Manhattan distance. Thus, these algorithms were inefficient to quantify the similarity of TAD images due to their low consistence rate.

FIG. 5.

The results of image distance and image similarity measurement. (a) The heatmap of Euclidean distance and the Manhattan distance. (b) The data distribution of Euclidean distance and the Manhattan distance. (c) The heatmap of four image similarity measurement. (d) The data distribution of Jaccard similarity, Hamming similarity, Pearson correlation, and Cosine similarity.

FIG. 6.

Consistence rate of all algorithms. The “S” in parentheses indicates that the method is sequence based. (a) Consistence rate of 4 classes of 17 algorithms. Category I is classic algorithms, category II is sequence-based statistical algorithms, category III is image hash algorithms, category IV is image statistical algorithms. (b) Consistence rate of each algorithm. JI_Sim is Jaccard similarity, HM_Sim is Hamming similarity, Pearson_Corr is Pearson correlation, Cos_Sim is Cosine similarity, BP(S) is BP distance, VI(S) is VI distance, ED(S) is Euclidean distance, CD(S) is Chebyshev distance, JI(S) is JI distance, HD(S) is Hamming distance, and MD is Manhattan distance.

2.3.5. Consistence rate comparison

The consistence rate of four classes was calculated (Fig. 6a). In the four major categories, the performance of image statistical algorithms in TAD similarity quantization was satisfactory. Three out of eight showed 100% consistence. Image hash algorithms with the best zoom size took the second place. And the dHash with 512 × 512 was as consistent as 94.74%. The average consistence rate of sequence-based statistical algorithms was better than classic algorithms (Fig. 6a).

Seventeen algorithms' consistence rate was calculated (Fig. 6b). Among them, seven algorithms had better performance, and the consistence rate was higher than 60%. Image subtraction, Euclidean distance, and Manhattan distance in image statistical algorithms had the highest consistence rate, that is, 100%. Second, the consistence rate of dHash algorithm in image hash algorithms with the best zoom size was 94.74%. Third, the consistence rate of hamming distance in sequence-based statistical algorithms was 84.21%. Fourth, JI distance algorithm in classic algorithms was 73.68%. In contrary, the performance of pHash algorithm, hamming distance in image statistical algorithms, Jaccard similarity, Pearson correlation coefficient, cosine similarity, etc. was not as good as other algorithms for the quantization of TAD similarity due to their low consistence rate.

3. Discussion

TADs are very important parts of chromatin hierarchy (Pope et al., 2014). TADs contain sub-TADs, which form a hierarchical structure at the TAD level (Xianglin et al., 2018). The destruction of TAD structure leads to the disorder of gene regulation, which may cause disease (Lupianez et al., 2015; Franke et al., 2016; Valton and Dekker, 2016). In recent years, TADs have been studied in a variety of biological backgrounds to explore their role in normal and disease development (Zufferey et al., 2018). However, the success and reliability of these studies depend on the ability to identify these domains correctly (Zufferey et al., 2018). So, a lot of tools to call TADs has been developed to provide a guarantee for the success and reliability of these studies. However, few algorithms were provided to compare the similarity of TADs. And the hierarchy of TADs is complex (Xianglin et al., 2018), so that the identification of TADs could help to understand the spatial relationship of the local chromatin region and to investigate the potential relationship between the regulatory element and the gene (Xianglin et al., 2018). The similar genomic structure may have a similar relationship between the regulatory element and the gene. Therefore, it is of great significance to study the similarity of TAD quantization method.

In this article, 17 algorithms from 4 kinds to measure the similarity of TADs from the point of sequence and image were compared. And the advantages and disadvantages of these 17 methods were summarized.

In the first category, three classical methods were compared. Among them, JI distance was to identify and quantify regions of chromosomes where TAD arrangement was (dis)similar between two experiments (Zaborowski and Wilczynski, 2019). The principle was to calculate the overlap degree of the TAD boundary (Zaborowski and Wilczynski, 2019). It was a widely used method of TAD quantization. The advantage of this method was that the operation was simple and computationally fast. But its disadvantages were also obvious. This approach had a serious drawback, that was, large domains with relatively small shift in their boundaries contributed to lowering the overall dissimilarity, as was the case with small domains leading to relatively large shifts (Zaborowski and Wilczynski, 2019). But VI distance based on information entropy (Filippova et al., 2014) was a method to overcome this shortcoming. It was a kind of nonboundary-centric measurement method, which mainly measured the variation of information (Zaborowski and Wilczynski, 2019).

However, the disadvantage of this approach was that it did not take the linear structure of the genome into account and usually deviates from the random control and, therefore, overestimated highly conservative structures (Zaborowski and Wilczynski, 2019). Another method was BPscore, which was a proper metric satisfying triangle inequality (Zaborowski and Wilczynski, 2019). BPscore was a relatively simple distance metric, which was a distance metric based on the bipartite matching between two segmentations (Zaborowski and Wilczynski, 2019). The advantage of this method was that the resolution was adjusted naturally with the size of the chromosome when the segments were separated (Zaborowski and Wilczynski, 2019). In addition, the method dealt with various changes (insertions, deletions, and shifts of domain boundaries) equally, which could be used to compare domain sets with different granularity (Zaborowski and Wilczynski, 2019).

The second category methods, sequence-based statistical algorithms, were mainly based on the sequence of statistical methods, including hamming distance, Euclidean distance, and Chebyshev distance. The principle of these methods was similar to the JI distance, that was, to compare the degree of the overlap or the degree of the differences between the TAD boundary. The merits and demerits were as same as JI distance. The image hash algorithms and image statistical algorithms were used to quantify the TAD similarity by comparing the similarity of the images after generating the TAD images. Visualization could show the spatial structure of TADs more intuitively. The information of each pixel was made full use. And the similarity and differences between TADs were compared to the maximum extent. These were merits of image hash algorithms and image statistical algorithms. However, the disadvantages of these two category methods were obvious, that was, the information of the image was stored in the pixel, and the scaling of the image may result in the loss of the information.

Through the comparison of 17 TAD similarity quantization algorithms from 4 kinds, it's found that the image-based method was superior to the sequence-based method. Ranked by consistence rate, the top seven were image difference, Euclidean distance, Manhattan distance, dHash with best zoom size, hamming distance attached with best 200 M size, and JI distance. Among these seven algorithms with the highest consistence rate, image-based method accounted for five, showing superior performance. Although part of the information would be lost when the image size was scaled, the impact could be minimized by controlling the scaling multiple of the image. And by comparing the differences of all the corresponding pixels between the two images, the similarity could be quantified to the maximum extent. The other two methods, hamming distance and JI distance, also had their commonality. They all quantify the similarity of TADs by calculating the overlap of TAD boundaries. Although these two methods were relatively simple, they fully considered the linear structure and conservative structure of the gene.

Although this study had compared the advantages and disadvantages of 17 algorithms in an all-round way, it also has some limitations. In terms of test data selection, four sets of data were selected, namely, identical sample pairs, biological duplicate sample pairs, different endonuclease sample pairs, and different cell line sample pairs. Since the identical sample pairs were few, the same sample was used to pair itself (Group A). Therefore, there is no experimental error or operating error; the distance between the sample pairs was 0 or the similarity was 1. The differences between biological duplicate sample pairs (Group B) and different endonuclease sample pairs (Group C) were small; the distance or similarity was similar. So, the degree of differentiation was not very well. This could not be the perfect choice, but in theory, it is true that the similarity of TADs between group A and group D should decrease or increase in distance.

In general, we compared 17 TAD similarity algorithms from four categories with two different angles of sequence and image and presented the advantages and disadvantages of these algorithms in an all-round way. Among these four categories of algorithms, image statistical algorithms were superior. Three out of eight of image statistical algorithms had a consistence rate of 100%. The average consistence rate of image hash algorithms with the best zoom size was 71.93%, which took the second place, followed by sequence-based statistical algorithms with consistence rate of 56%. The average consistence rate of classic algorithms was slightly lower than sequence-based statistical algorithms, which was 50.87%. Although these algorithms involved in this study were relatively simple, it is the first time to compare the similarity of TADs from many angles and provide references for the TAD similarity measurement from the field of image science.

Footnotes

Acknowledgments

The authors thank Lingxiao Zhou, Yingying Liu, and Wen Yuan for the critical feedback and discussions. Funding: This work was supported by the National Key Research and Development Program of China (no. 2016YFC0901903).

Data Availability Statement

All data used can be found at GEO ().

Authors' Contributions

A.W. downloaded data from GEO and preprocessed these data. A.W. called topological associating domains. Y.L. performed subsequent analyses with 17 algorithms for quantifying the genomic similarity of topological associating domains. G.L. and L.L. designed the study. Y.L. wrote the article. All authors read and approved the final article.

Author Disclosure Statement

The authors declare there are no conflicting financial interests.

Supplementary Material

References

Bay

, Tuytelaars

, and Van Gool

2006. Surf: Speeded up robust features. European Conference on Computer Vision. 3951, 405–417.

Birchfield

, and Tomasi

1999. Depth discontinuities by pixel-to-pixel stereo computer. Int. J. Comput. Vision, 3, 269–293.

Chait

B.T.

2011. Mass spectrometry in the postgenomic era. J. Annu. Rev. Biochem. 80, 239–246.

Dekker

, Rippe

, Dekker

, et al. 2002. Capturing chromosome conformation. J. Sci. 295, 1306–1311.

Dixon

J.R.

, Selvaraj

, Yue

, et al. 2012. Topological domains in mammalian genomes identified by analysis of chromatin interactions. J. Nat. 485, 376–380.

Dostie

, Richmond

T.A.

, Arnaout

R.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.

Durand

N.C.

, Robinson

J.T.

, Shamim

M.S.

, et al. 2016. Juicebox provides a visualization system for Hi-C contact maps with unlimited zoom. J. Cell Syst. 3, 99–101.

Fangping

2012. Depth Information Extraction Based On Binocular Stereo Vision System. Beijing Jiaotong University, Beijing.

Filippova

, Patro

, Duggal

, et al. 2014. Identification of alternative topological domains in chromatin. J. Algorithms Mol. Biol. 9, 14.

10.

Franke

, Ibrahim

D.M.

, Andrey

, et al. 2016. Formation of new chromatin domains determines pathogenicity of genomic duplications. J. Nat. 538, 265–269.

11.

Haitian

2015. Research on Stereo Matching Algorithm in Stereo Vision Ranging. Xidian University, Xi'an.

12.

Jiaheng

, Xiaowei

, Benhui

, et al. 2017. A comparative study of image similarity algorithms based on Hash. J. Dali Univ. 2, 32–37.

13.

Jiawei

, Zhiqiang

, and Shuyan

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.

Kaur

, Kaur

, and Kaur

2014. Detection and classification of printed circuit board defects using image subtraction method. IEEE, Chandigarh, India. pp. 1–5.

15.

Lieberman-Aiden

, van Berkum

N. L.

, Williams

, et al. 2009. Comprehensive mapping of long-range interactions reveals folding principles of the human genome. J. Sci. 326, 289–293.

16.

Lowe

D.G.

2004. Distinctive image features from scale-invariant key point. Int. J. Comput. 60, 91–110.

17.

Lupianez

D.G.

, Kraft

, Heinrich

, et al. 2015. Disruptions of topological chromatin domains cause pathogenic rewiring of gene-enhancer interactions. J. Cell, 161, 1012–1025.

18.

Pope

B.D.

, Ryba

, Dileep

, et al. 2014. Topologically associating domains are stable units of replication-timing regulation. J. Nat. 515, 402–405.

19.

Qiongyang

, and Lifang

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.

Rao

S.S.

, Huntley

M.H.

, Durand

N.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.

Risca

V.I.

, and Greenleaf

W.J.

2015. Unraveling the 3D genome: Genomics tools for multiscale exploration. J. Trends Genet. 31, 357–372.

22.

Sauerwald

, and Kingsford

2018. Quantifying the similarity of topological domains across normal and cancer human cell types. J. Bioinformatics, 34, i475–i483.

23.

Schmitt

A.D.

, Hu

, and Ren

2016. Genome-wide mapping and analysis of chromosome architecture. J. Nat. Rev. Mol. Cell Biol. 17, 743–755.

24.

Serra

, Bau

, Goodstadt

, 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.

Servant

, Lajoie

B.R.

, Nora

E.P.

, et al. 2012. HiTC: Exploration of high-throughput ‘C’ experiments. J. Bioinformatics, 28, 2843–2844.

26.

Servant

, Varoquaux

, Lajoie

B.R.

, et al. 2015. HiC-Pro: An optimized and flexible pipeline for Hi-C data processing. J. Genome Biol. 16, 259.

27.

Shen

, Zhimin

, and Nan

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.

Simonis

, Klous

, Splinter

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.

Valton

A.L.

, and Dekker

2016. TAD disruption as oncogenic driver. J. Curr. Opin. Genet. Dev. 36, 34–40.

30.

Wang

, Sun

, Czajkowsky

D.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.

Weinreb

, and Raphael

B.J.

2016. Identification of hierarchical chromatin domains. J. Bioinformatics, 32, 1601–1609.

32.

, Li

, et al. 2017. 3D genome of multiple myeloma reveals spatial genome disorganization associated with copy number variations. J. Nat. Commun. 8, 1937.

33.

Xianglin

, Huan

, and Xiaowo

2018. Progress in three-dimensional Genome data Analysis. J. Prog. Biochem. Biophys. 45, 1093–1105.

34.

Xiaogang

, Fei

, Dong

, et al. 2005. Study on the image grayscale matching algorithm based on similarity measures. J. Syst. Eng. Electr. 27, 305–314.

35.

, and Ren

2017. The Three-Dimensional Organization of Mammalian Genomes. J. Annu. Rev. Cell Dev. Biol. 33, 265–289.

36.

Yubo

2018. Three-dimensional genomics and precise biology. J. Chin. Biochem. Mol. Biol. 34, 351–363.

37.

Yumei

, Yi

, and Junhui

2019. Research on image similarity retrieval algorithm based on color variance. J. Commun. Technol. 52, 74–79.

38.

Zaborowski

, and Wilczynski

2019. BPscore: an effective metric for meaningful comparisons of structural chromosome segmentations. J. Comput. Biol. 26.

39.

Zhao

, Tavoosidana

, Sjolinder

, 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.

Zufferey

, Tavernari

, Oricchio

, 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.

0.00 MB

0.30 MB