# Adjacency-constrained hierarchical clustering of a band similarity matrix with application to genomics

Christophe Ambroise, Alia Dehman, Pierre Neuvial, Guillem Rigaill, Nathalie Vialaneix

<figure><img src="image_1.png" /></figure>

To cite this version:

Christophe Ambroise, Alia Dehman, Pierre Neuvial, Guillem Rigaill, Nathalie Vialaneix. Adjacency-constrained hierarchical clustering of a band similarity matrix with application to genomics. Statistical Methods for Post Genomic Data (SMPGD 2019), Jan 2019, Barcelona, Spain. 2019. hal-02790995

HAL Id: hal-02790995

https://hal.inrae.fr/hal-02790995

Submitted on 5 Jun 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License
# Adjacency-constrained hierarchical clustering of a band similarity matrix with application to genomics

Christophe Ambroise<fnref n="1" />, Alia Dehman<fnref n="2" />, **Pierre Neuvial**<fnref n="3" />, Guillem Rigaill<fnref n="4" /> and Nathalie Vialaneix<fnref n="5" />

¹LaMME, Evry • ²Hyphen-stat, Toulouse • ³Institut de Mathématiques de Toulouse/CNRS • ⁴IPS2, CNRS/INRA • ⁵INRA MIAT •

## Motivation: Regionally-structured genomic data

### Genome-Wide Association Studies (GWAS)

* loci: SNP

* similarity: linkage disequilibrium

* regions: LD/haplotype blocks

<figure><img src="image_3.png" /></figure>

### Chromosome contact maps (Hi-C)

* loci: binned genome positions

* similarity: contact intensity

* regions: TAD; A/B compartments

<figure><img src="image_4.png" /></figure>

## Goal: Segmentation by constrained HAC

### Hierarchical Agglomerative Clustering (HAC)

* Input: *p* objects, similarity *S*

* Repeat *p* — 1 times: merge the most similar clusters

* Output: A dendrogram describing the sequence of merges

<figure><img src="image_5.png" /></figure>

### Adjacency-constrained HAC: only merge adjacent clusters

* Improved time complexity: quadratic (*O*(*p*<fnref n="2" />))

* Space complexity (*O*(*p*<fnref n="2" />)): can be improved in specific applications<fnref n="1" />

Still too high for Hi-C, GWAS: *p* ~ 10⁴ – 10⁵ for each chromosome.

## Contribution: a quasi-linear algorithm<fnref n="2" />

Extra assumption: band diagonal similarity

## Key 1: Ward's linkage in constant time

### Distance between clusters: Ward's linkage

$$ \delta(C, C') = \frac{S(C)}{|C|} + \frac{S(C')}{|C'|} - \frac{S(C \cup C')}{|C \cup C'|}, \quad S(C) = \sum_{(i,j) \in C^2} s_{ij} $$

<figure><img src="image_6.png" /></figure>

<figure><img src="image_7.png" /></figure>

## Key 2: Storing candidate fusions in a min-heap

### Min heap

#### A partially ordered binary tree

* nodes = candidate merges

* ordering given by the linkage δ

→ next candidate fusion is the root of the heap

#### Complexity

* $O(p^h)$ in space

* $O(p(h + \log(p))$ in time

<figure><img src="image_8.png" /></figure>

## Implementation

### R package adjclust<fnref n="3" />

* plots of similarity, dendrogram and clustering

* wrappers for SNP or Hi-C data analyses

* model selection by broken stick<fnref n="4" /> or slope heuristic<fnref n="5" />

## GWAS: inferring linkage disequilibrium blocks

### Band approximation

Quality index: proportion of approximation vs *h*

<figure><img src="image_9.png" /></figure>

### Scalability

<figure><img src="image_10.png" /></figure>

Data from [⁶]

## Hi-C: inferring Topologically Associated Domains

### Influence of bandwidth

<figure><img src="image_11.png" /></figure>

Data from [⁷] and [⁸]

### DI around clusters

<figure><img src="image_12.png" /></figure>

Directionality Index (DI, [⁷]) values are expected to show a sharp variation at TADs boundaries

## References

<footnote n="1">¹ A. Dehman, C. Ambroise, and P. Neuvial, BMC Bioinformatics **16**, 148 (2015).</footnote>

<footnote n="2">² C. Ambroise, A. Dehman, P. Neuvial, G. Rigaill, and N. Vialaneix, (2019).</footnote>

<footnote n="3">³ C. Ambroise and others, Adjclust: Adjacency-Constrained Clustering of a Block-Diagonal Similarity (2018).</footnote>

<footnote n="4">⁴ K.D. Bennett, New Phytologist **132**, 155 (1996).</footnote>

<footnote n="5">⁵ S. Arlot, V. Brault, J.-P. Baudry, and others, Capushe: Calibrating Penalties Using Slope Heuristics (2016).</footnote>

<footnote n="6">⁶ C. Dalmasso, W. Carpentier, L. Meyer, and others, PLoS ONE **3**, (2008).</footnote>

<footnote n="7">⁷ J. Dixon, S. Selvaraj, F. Yue, A. Kim, Y. Li, Y. Shen, M. Hu, J. Liu, and B. Ren, Nature **485**, 376 (2012).</footnote>

<footnote n="8">⁸ Y. Shen, F. Yu, D.F. McCleary, Z. Ye, L. Edsall, and others, Nature **488**, 116 (2012).</footnote>