GraphHDBSCAN*: Graph-based Hierarchical Clustering on High Dimensional Single-cell RNA Sequencing Data

Ce papier présente GraphHDBSCAN*, une méthode de clustering hiérarchique basée sur les graphes et sans hyperparamètres qui améliore l'identification des populations cellulaires et de leur organisation hiérarchique dans les données de séquençage de l'ARN monocellulaire.

L'essentiel

🧬 Le Grand Puzzle des Cellules : Comment GraphHDBSCAN* met de l'ordre dans le chaos

Imaginez que vous êtes dans une immense salle de bal remplie de millions de danseurs. Chaque danseur représente une cellule de votre corps. Certains dansent le tango, d'autres le hip-hop, d'autres encore le slow. Le problème ? La musique est très forte, la lumière est clignotante, et il y a des milliers de danseurs qui bougent de manière très similaire.

C'est ce que les scientifiques appellent le séquençage ARN de cellule unique (scRNA-seq). Ils veulent comprendre qui est qui, mais les données sont un véritable chaos : très nombreuses, très complexes et souvent bruyantes (comme si certains danseurs avaient mal aux pieds ou portaient des chaussures trop grandes).

Jusqu'à présent, les outils pour trier ces danseurs avaient deux gros défauts :

1. Ils étaient trop simples : Ils forçaient tout le monde à choisir un seul style de danse (un "groupe" plat), ignorant le fait que le tango a des sous-genres (tango argentin, tango espagnol, etc.).
2. Ils étaient fragiles : Un petit changement dans les réglages (comme changer le volume de la musique) pouvait tout mélanger.

C'est ici qu'intervient GraphHDBSCAN*, le nouvel outil présenté dans cet article. Voici comment il fonctionne, avec des analogies simples.

---

1. La Carte des Amis (Le Graphe) 🗺️

Au lieu de regarder chaque danseur isolément, GraphHDBSCAN* regarde qui est ami avec qui.

• L'analogie : Imaginez que vous dessinez des lignes entre les danseurs qui se ressemblent beaucoup. Plus ils se ressemblent, plus la ligne est épaisse et solide.
• Le génie de l'outil : Dans un monde à 3 dimensions, c'est facile de voir qui est proche. Mais avec des millions de dimensions (des milliers de gènes), la "distance" devient trompeuse. GraphHDBSCAN* utilise une astuce appelée WSS (Similarité Structurelle Pondérée). C'est comme dire : "Ce n'est pas seulement que tu es proche de Paul, c'est que tu es proche de Paul, Marie et Luc, et que Paul, Marie et Luc sont aussi proches entre eux." Cela crée une carte de relations beaucoup plus fiable que de simples distances.

2. L'Arbre Généalogique au lieu d'une Liste Plate 🌳

Les anciennes méthodes (comme Louvain ou Leiden) vous donnaient une liste plate : "Voici les groupes 1, 2 et 3". C'est comme dire : "Voici les animaux : Chien, Chat, Oiseau".
GraphHDBSCAN*, lui, construit un arbre généalogique (une hiérarchie).

• L'analogie : Au lieu de juste dire "Chien", l'arbre vous montre :
  • Au sommet : "Mammifères".
  • En descendant : "Carnivores".
  • Plus bas : "Chiens".
  • Tout en bas : "Golden Retriever", "Bouledogue", "Chihuahua".
• Pourquoi c'est génial ? Cela permet de voir à la fois la grande famille (les globules blancs) et les petits détails (les sous-types de monocytes) sans avoir à choisir à l'avance quel niveau de détail on veut. C'est comme avoir une loupe qui s'adapte automatiquement.

3. Le "Filtre Magique" sans Réglages 🎛️

Habituellement, pour trier des données, il faut régler des boutons (des "hyperparamètres"). Si vous tournez trop fort, vous cassez les groupes ; pas assez, et tout reste mélangé. C'est comme essayer de régler le volume d'une radio sans savoir où est le bouton.

• La solution : GraphHDBSCAN* utilise une technique appelée CORE-SG. C'est comme si l'outil calculait tous les réglages possibles en même temps d'un seul coup. Il vous donne une famille entière d'arbres hiérarchiques. Vous pouvez ensuite explorer librement : "Montre-moi les grands groupes" ou "Montre-moi les sous-groupes fins", sans jamais avoir à relancer le calcul. C'est un outil "sans réglages" dans la pratique.

4. Sauver les Perdus (Le Propagation d'Étiquettes) 🏷️

Dans ces données bruyantes, certaines cellules sont si étranges que les algorithmes classiques les jettent dans une poubelle étiquetée "Bruit" (Noise). Mais en biologie, ces "bruits" sont parfois des cellules rares et précieuses, ou simplement des cellules mal classées par erreur.

• L'analogie : Imaginez un groupe de musique où un membre a perdu sa partition. Au lieu de le renvoyer chez lui, GraphHDBSCAN* utilise une technique de propagation d'étiquettes. Il regarde autour de ce membre perdu : "Tiens, il ressemble beaucoup aux guitaristes, et il est assis juste à côté d'eux. Il doit être un guitariste !"
• Le résultat : Il réattribue intelligemment ces cellules "perdues" au groupe le plus logique, en se basant sur la densité et la structure, sans perdre d'information.

---

🏆 Pourquoi c'est une révolution ?

L'article compare GraphHDBSCAN* aux champions actuels (Louvain, Leiden, HDBSCAN* classique) sur de nombreux jeux de données réels (sang, embryons, etc.).

• Résultat : GraphHDBSCAN* gagne souvent la course. Il retrouve mieux les structures biologiques réelles (comme la différence subtile entre deux types de cellules immunitaires) et produit des groupes plus stables.
• L'avantage clé : Il ne force pas la réalité dans un moule plat. Il accepte que la vie soit hiérarchique et complexe.

En résumé 📝

Si les anciennes méthodes étaient comme un tri postal qui classe les lettres dans des boîtes rigides (A, B, C), GraphHDBSCAN* est comme un arbre généalogique vivant. Il comprend que les familles se divisent, se regroupent et ont des nuances. Il est robuste, ne nécessite pas de réglages manuels complexes, et surtout, il ne jette personne à la poubelle : il s'assure que chaque cellule trouve sa place dans l'histoire de la vie.

C'est un outil puissant pour décoder la complexité de la vie, cellule par cellule.

Résumé technique

1. Problématique

Le séquençage de l'ARN à l'échelle d'une seule cellule (scRNA-seq) a révolutionné la biologie en permettant d'analyser l'hétérogénéité cellulaire à travers des millions de cellules. Cependant, l'analyse de ces données pose des défis computationnels majeurs :

• Dimensionnalité et Sparsité : Les données sont extrêmement haute dimensionnelles et bruitées, ce qui rend les mesures de distance classiques (comme la distance euclidienne) peu informatives (malédiction de la dimensionnalité).
• Structure Hiérarchique : Les types cellulaires ne forment pas seulement des partitions plates ; ils possèdent une organisation hiérarchique naturelle (ex: un type cellulaire large se divisant en sous-types spécialisés).
• Limites des méthodes actuelles :
  • Les méthodes de détection de communautés basées sur la modularité (Louvain, Leiden), standards dans des outils comme Seurat et SCANPY, produisent uniquement des partitions plates. Elles ignorent la structure hiérarchique et sont sensibles aux hyperparamètres (notamment le paramètre de résolution).
  • Les méthodes de clustering hiérarchique basées sur la densité (comme HDBSCAN*) sont théoriquement adaptées pour gérer des densités variables et identifier le bruit, mais leur application directe aux données scRNA-seq est inefficace en raison de la faible qualité des distances dans les espaces de haute dimension, conduisant souvent à une sur-estimation du bruit (beaucoup de cellules rejetées comme "bruit").

2. Méthodologie : GraphHDBSCAN*

Les auteurs proposent GraphHDBSCAN, une extension basée sur les graphes de l'algorithme HDBSCAN, conçue spécifiquement pour les données scRNA-seq.

A. Construction du Graphe (Représentation des Données)

Au lieu d'opérer directement sur les distances brutes dans l'espace des caractéristiques, la méthode construit une représentation graphique robuste :

1. Graphe k-NN : Construction initiale d'un graphe des $k$ plus proches voisins à partir des données brutes (expression génique).
2. Similarité Structurelle Pondérée (WSS - Weighted Structural Similarity) :
   • La méthode généralise le concept de Shared Nearest Neighbors (SNN) et l'algorithme SCAN (Structural Clustering Algorithm for Networks) aux graphes pondérés.
   • Elle calcule une similarité entre les nœuds en tenant compte non seulement du chevauchement des voisins, mais aussi du poids des arêtes (force de la connexion).
   • Cette transformation permet de capturer la structure locale de manière plus stable que les distances brutes, atténuant l'impact de la haute dimensionnalité.
3. Conversion en Dissimilarité : Les poids de similarité sont transformés en dissimilarités ($d = 1 - sim$) pour être compatibles avec les concepts de HDBSCAN*.

B. Clustering Hiérarchique Densité-Basé

• Adaptation de HDBSCAN :* L'algorithme HDBSCAN* est appliqué directement sur le graphe WSS. Les distances de mutual reachability et les distances de cœur (core distances) sont calculées en utilisant les poids des arêtes du graphe.
• Efficacité avec CORE-SG : Pour explorer efficacement différentes échelles de densité (différentes valeurs de l'hyperparamètre minPts), la méthode utilise le cadre CORE-SG (Core-distance based Spanning Graph). Cela permet de dériver une famille entière de hiérarchies à partir d'un seul calcul initial, rendant l'algorithme pratiquement sans paramètre pour l'utilisateur final (bien que la construction du graphe nécessite des paramètres).
• Extraction de Partition Plate : Une partition plate (non hiérarchique) est extraite de l'arbre condensé en utilisant le critère FOSC (Framework for Optimal Selection of Clusters) basé sur l'excès de masse (EOM), favorisant les clusters stables.

C. Gestion du Bruit et Propagation d'Étiquettes

• Contrairement à HDBSCAN* standard qui rejette souvent les points comme du bruit, GraphHDBSCAN* intègre une étape de propagation d'étiquettes (Label Propagation).
• Basée sur une classification semi-supervisée ($HDBSCAN^*(cd, -)$), cette étape réattribue les points identifiés comme "bruit" aux clusters les plus denses accessibles via l'arbre couvrant minimal (MST). Cela permet d'obtenir une partition complète de l'ensemble des cellules tout en conservant les points bruyants pour une analyse ultérieure si nécessaire.

3. Contributions Clés

1. Nouvelle Méthode Hiérarchique : Introduction de GraphHDBSCAN*, capable de récupérer à la fois des partitions plates de haute qualité et des hiérarchies interprétables sans nécessiter de réduction de dimension préalable (PCA, t-SNE, UMAP).
2. Robustesse aux Données Haute Dimension : L'utilisation de la similarité structurelle pondérée (WSS) sur un graphe permet de surmonter les limitations des distances euclidiennes dans les données scRNA-seq.
3. Sans Paramètre (Hyperparameter-free) : Grâce à CORE-SG, la méthode explore automatiquement un large éventail de densités, éliminant le besoin de régler manuellement des paramètres critiques comme la résolution dans Louvain/Leiden.
4. Gestion Avancée du Bruit : Une stratégie de propagation d'étiquettes basée sur la densité permet de "sauver" les cellules identifiées comme bruit, les assignant aux sous-populations les plus probables, tout en permettant d'identifier les artefacts techniques (comme les doublets).
5. Interprétabilité Biologique : La méthode produit des arbres hiérarchiques qui reflètent directement les lignées cellulaires biologiques connues.

4. Résultats et Évaluation

Les auteurs ont évalué GraphHDBSCAN* sur plusieurs jeux de données scRNA-seq publics (incluant des données de cellules sanguines, embryonnaires et de lignées cellulaires).

• Reconstruction Biologique :
  • Sur des données de cellules mononucléées du sang périphérique (PBMC), la méthode a correctement séparé les lignées majeures (Monocytes, T CD4, T CD8, NK, B) et a révélé des sous-populations fines non décrites dans les études originales (ex: deux sous-types de monocytes distincts validés par des marqueurs protéiques CD36 et CD11c).
  • La hiérarchie récupérée correspond bien aux ontologies cellulaires connues (différenciation hématopoïétique).
• Performance de Partition Plate (Benchmark) :
  • Comparé aux méthodes de référence (Louvain, Leiden, HDBSCAN* original), GraphHDBSCAN* obtient des scores supérieurs ou compétitifs sur les métriques ARI (Adjusted Rand Index) et AMI (Adjusted Mutual Information).
  • Contrairement à Louvain/Leiden, GraphHDBSCAN* montre une variabilité plus faible et une robustesse supérieure, même avec ses paramètres par défaut non optimisés spécifiquement pour le scRNA-seq.
  • HDBSCAN* original performe nettement moins bien, confirmant la nécessité de l'approche basée sur le graphe.
• Efficacité Computationnelle :
  • Bien que légèrement plus coûteux que Louvain/Leiden en raison de la construction de la hiérarchie, GraphHDBSCAN* présente une mise à l'échelle (scaling) lisse et reste pratique pour des ensembles de données de grande taille (jusqu'à plusieurs milliers de cellules en temps réel, et des millions avec une mise à l'échelle appropriée).

5. Signification et Impact

Ce travail comble un vide important dans l'analyse du scRNA-seq en offrant une alternative robuste aux méthodes de partitionnement plat dominantes.

• Préservation de la Structure : Il permet aux biologistes de visualiser et d'analyser les relations hiérarchiques entre les types cellulaires (ex: comment un progéniteur se divise en sous-types matures) sans recourir à des techniques de visualisation 2D/3D qui peuvent déformer la topologie des données.
• Fiabilité : En réduisant la sensibilité aux hyperparamètres et en améliorant la gestion du bruit, GraphHDBSCAN* offre une reproductibilité accrue.
• Flexibilité : La capacité d'obtenir à la fois une vue d'ensemble hiérarchique et une partition plate de haute qualité en fait un outil polyvalent pour l'exploration de données complexes.

En résumé, GraphHDBSCAN* représente une avancée significative en combinant la théorie du clustering basé sur la densité avec la robustesse des graphes de similarité structurelle, offrant une solution "tout-en-un" pour l'analyse hiérarchique et plate des données transcriptomiques à l'échelle cellulaire.