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.
Origin : Files produced by the author(s)
