Fast tree aggregation for consensus hierarchical clustering - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Article Dans Une Revue BMC Bioinformatics Année : 2020

Fast tree aggregation for consensus hierarchical clustering

Résumé

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.
Fichier principal
Vignette du fichier
2020_Hulot_BMC Bioinformatics.pdf (1.1 Mo) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Licence : CC BY - Paternité

Dates et versions

hal-02961035 , version 1 (12-03-2021)

Identifiants

Citer

Audrey Hulot, Julien Chiquet, Florence Jaffrezic, Guillem Rigaill. Fast tree aggregation for consensus hierarchical clustering. BMC Bioinformatics, 2020, 21 (1), ⟨10.1186/s12859-020-3453-6⟩. ⟨hal-02961035⟩
167 Consultations
46 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More