Journal
ALGORITHMS FOR MOLECULAR BIOLOGY
Volume 14, Issue 1, Pages -Publisher
BMC
DOI: 10.1186/s13015-019-0157-4
Keywords
Hierarchical agglomerative clustering; Adjacency constraint; Segmentation; Ward's linkage; Similarity; Min heap; Genome-Wide Association Studies and Hi-C
Categories
Funding
- CNRS project SCALES (Mission Osez l'interdisciplinarite)
- Genopole
Ask authors/readers for more resources
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 implementation of adjacency-constrained HAC with quasi-linear complexity. This is achieved by pre-calculating specific sums of similarities, and storing candidate fusions in a min-heap. Our illustrations on GWAS and Hi-C datasets demonstrate the relevance of this assumption, and show that this method highlights biologically meaningful signals. Thanks to its small time and memory footprint, the method can be run on a standard laptop in minutes or even seconds. Availability and implementation: Software and sample data are available as an R package, adjclust, that can be downloaded from the Comprehensive R Archive Network (CRAN).
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available