Skip to Main content Skip to Navigation
Poster communications

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

Abstract : We focus on a modification of the classical hierarchical agglomerative clustering (HAC), where only adjacent clusters (according to the ordering of positions within a chromosome) can be merged. Adjacency-constrained HAC is implemented in the R package rioja. Our main contribution with respect to existing works is an efficient implementation of adjacency-constrained HAC in the case where the similarity between genomically distant objects can be considered as negligible. We propose an algorithm that is almost linear in time and space with respect to the number of objects to be clustered. It uses a sparse band strategy based on pre-computations of certain cumulative sums of similarities, combined with a min-heap approach to efficiently store and maintain a list of candidate merges. This algorithm is implemented in the R package adjclust, which is available at https://CRAN.R-project.org/package=adjclust. We provide applications to SNP and Hi-C datasets.
Complete list of metadata

https://hal.inrae.fr/hal-02790995
Contributor : Migration ProdInra Connect in order to contact the contributor
Submitted on : Friday, June 5, 2020 - 7:05:38 AM
Last modification on : Wednesday, June 15, 2022 - 3:48:53 AM

File

ambroise_etal_SMPGD2019-poster...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - ShareAlike 4.0 International License

Identifiers

  • HAL Id : hal-02790995, version 1
  • PRODINRA : 466078

Citation

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⟩

Share

Metrics

Record views

16

Files downloads

12