Skip to Main content Skip to Navigation
Journal articles

Fast tree aggregation for consensus hierarchical clustering

Abstract : Background In unsupervised learning and clustering, data integration from different sources and types is a difficult question discussed in several research areas. For instance in omics analysis, dozen of clustering methods have been developed in the past decade. When a single source of data is at play, hierarchical clustering (HC) is extremely popular, as a tree structure is highly interpretable and arguably more informative than just a partition of the data. However, applying blindly HC to multiple sources of data raises computational and interpretation issues. Results We propose mergeTrees, a method that aggregates a set of trees with the same leaves to create a consensus tree. In our consensus tree, a cluster at height h contains the individuals that are in the same cluster for all the trees at height h. The method is exact and proven to be \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathcal {O}(nq\log (n))$\end{document}O(nqlog(n)), n being the individuals and q being the number of trees to aggregate. Our implementation is extremely effective on simulations, allowing us to process many large trees at a time. We also rely on mergeTrees to perform the cluster analysis of two real -omics data sets, introducing a spectral variant as an efficient and robust by-product. Conclusions Our tree aggregation method can be used in conjunction with hierarchical clustering to perform efficient cluster analysis. This approach was found to be robust to the absence of clustering information in some of the data sets as well as an increased variability within true clusters. The method is implemented in R/C++ and available as an R package named mergeTrees, which makes it easy to integrate in existing or new pipelines in several research areas.
Complete list of metadata

https://hal.inrae.fr/hal-02961035
Contributor : Guillem Rigaill Connect in order to contact the contributor
Submitted on : Friday, March 12, 2021 - 1:25:52 PM
Last modification on : Tuesday, September 28, 2021 - 5:13:16 PM

Citation

Audrey Hulot, Julien Chiquet, Florence Jaffrézic, Guillem Rigaill. Fast tree aggregation for consensus hierarchical clustering. BMC Bioinformatics, BioMed Central, 2020, 21 (1), ⟨10.1186/s12859-020-3453-6⟩. ⟨hal-02961035⟩

Share

Metrics

Record views

192

Files downloads

156