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

ABSTRACT:

Background

Genomic data analyses such as Genome-Wide Association Studies (GWAS) or Hi-C studies are often faced with the problem of partitioning chromosomes into successive regions based on a similarity matrix of high-resolution, locus-level measurements. An intuitive way of doing this is to perform a modified Hierarchical Agglomerative Clustering (HAC), where only adjacent clusters (according to the ordering of positions within a chromosome) are allowed to be merged. But a major practical drawback of this method is its quadratic time and space complexity in the number of loci, which is typically of the order of 10 4 to 10 5 for each chromosome.

Results

By assuming that the similarity between physically distant objects is negligible, we are able to propose an implementatio

SUBMITTER: Ambroise C 

PROVIDER: S-EPMC6857244 | biostudies-literature | 2019

REPOSITORIES: biostudies-literature