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

Il paper introduce GraphHDBSCAN*, un metodo di clustering gerarchico basato su grafi e privo di iperparametri progettato per identificare popolazioni cellulari biologicamente significative e le loro relazioni gerarchiche nei dati scRNA-seq ad alta dimensionalità, superando i limiti degli approcci attuali che si concentrano solo su partizioni piatte.

L'essenziale

Immagina di avere una stanza piena di milioni di persone (le cellule) che stanno tutte parlando contemporaneamente. Ognuna di queste persone ha un vocabolario unico (i geni che esprime) e, se ascolti attentamente, puoi capire chi sono, cosa fanno e come sono imparentate tra loro. Questo è il mondo della sequenziamento dell'RNA a cellula singola (scRNA-seq): una tecnologia potente che ci permette di vedere la vita a livello microscopico, ma che crea un caos di dati enorme.

Il problema? È come cercare di ordinare questa folla in gruppi logici (ad esempio, "tutti i medici", "tutti gli insegnanti", "tutti i bambini") quando:

1. Le persone sono così tante che è difficile tenere il conto.
2. La stanza è così grande e piena di rumore che le distanze tra le persone sembrano tutte uguali (il "curse of dimensionality").
3. Le relazioni non sono semplici: un "medico" può essere anche un "chirurgo specializzato", che a sua volta è un "neurochirurgo". È una gerarchia, non una lista piatta.

Fino a poco tempo fa, gli strumenti usati per ordinare questa folla (come Louvain o Leiden) facevano un lavoro decente, ma avevano due difetti:

• Erano "piatti": Ti dicevano "questi sono i medici" e "questi sono gli insegnanti", ma non ti mostravano come un medico generico si trasformi in un neurochirurgo.
• Erano sensibili alle impostazioni: Se cambiavi un piccolo interruttore (un parametro), il risultato cambiava completamente, come se la folla si riorganizzasse magicamente in modo diverso ogni volta.

L'Innovazione: GraphHDBSCAN*

Gli autori di questo articolo hanno creato un nuovo metodo chiamato GraphHDBSCAN*. Ecco come funziona, usando una metafora semplice:

1. La Mappa invece della Distanza

Invece di chiedere a ogni persona quanto è lontana da ogni altra persona (cosa impossibile con milioni di persone), GraphHDBSCAN* costruisce una mappa delle amicizie.

• Immagina che ogni persona tenga per mano solo le sue 10 o 20 persone più vicine (un grafo k-NN).
• Poi, invece di guardare solo chi tiene per mano chi, il metodo guarda quanto sono simili le loro reti di amici. Se tu e il tuo vicino avete molti amici in comune, siete probabilmente dello stesso "gruppo", anche se non vi conoscete direttamente. Questo si chiama Similarità Strutturale Pesata (WSS). È come dire: "Non importa quanto sei lontano da me in metri, importa quanto siamo simili nel nostro cerchio sociale".

2. La Piramide invece del Piano

Mentre gli altri metodi ti danno una sola foto della folla divisa in gruppi, GraphHDBSCAN* ti dà un albero genealogico completo.

• Immagina di guardare la folla da un elicottero. Da molto in alto, vedi solo due grandi gruppi: "Uomini" e "Donne".
• Scendi un po' più in basso e vedi: "Uomini adulti", "Uomini bambini", "Donne adulte", "Donne bambine".
• Scendi ancora e vedi: "Uomini adulti con i capelli biondi", "Uomini adulti con i capelli neri".
  GraphHDBSCAN* ti permette di esplorare questa gerarchia senza dover riavviare il computer ogni volta. Ti mostra come i gruppi si dividono e si fondono man mano che cambi la "risoluzione" della tua osservazione.

3. Il Salvataggio degli "Esclusi"

Spesso, nei dati biologici, ci sono cellule che sembrano "rumore" o "errori" (come se qualcuno nella folla avesse un megafono rotto o fosse un intruso). I vecchi metodi li buttavano via.
GraphHDBSCAN* ha un trucco speciale: se una cellula sembra un "rumore", usa un sistema di propagazione delle etichette. Immagina che le cellule "sane" passino un messaggio alle cellule "rumorose" vicine: "Ehi, sembri un po' confusa, ma se guardi chi ti sta intorno, probabilmente sei un medico come noi!". In questo modo, nessuna cellula viene lasciata sola; anche quelle difficili vengono assegnate al gruppo più probabile, salvando dati preziosi.

Perché è importante?

• Trova i dettagli nascosti: Nel loro studio, hanno scoperto sottogruppi di cellule (come specifici tipi di monociti) che i metodi precedenti non vedevano, proprio come se avessero trovato un nuovo quartiere in una città che pensavamo di conoscere già.
• È robusto: Funziona bene anche senza dover tarare manualmente decine di impostazioni. È come avere un GPS che trova il percorso migliore da solo, senza che tu debba dire "prendi la strada di sinistra" o "svolta a destra".
• È veloce: Nonostante faccia calcoli complessi, è abbastanza veloce da gestire milioni di cellule, rendendolo pratico per i laboratori di tutto il mondo.

In sintesi

Se i metodi precedenti erano come una fotografia piatta di una folla, GraphHDBSCAN* è come un film interattivo in 3D. Ti permette di zoomare dentro i gruppi, vedere le famiglie cellulari, capire chi è parente di chi e, soprattutto, non perdere nessuno nel processo. È uno strumento che trasforma un caos di dati biologici in una mappa chiara e comprensibile della vita stessa.

Sommario tecnico

1. Il Problema

L'analisi dei dati di sequenziamento dell'RNA a singola cellula (scRNA-seq) presenta sfide computazionali e biologiche significative:

• Dimensionalità e Sparsità: I dataset scRNA-seq sono estremamente sparsi e ad alta dimensionalità. In questi contesti, le metriche di distanza tradizionali diventano meno informative (il "curse of dimensionality"), rendendo difficile la stima della densità e la formazione di cluster robusti.
• Struttura Gerarchica: I dati biologici possiedono una struttura gerarchica intrinseca (es. tipi cellulari ampi che si dividono in sottotipi specializzati). Tuttavia, la maggior parte degli approcci attuali (come Louvain e Leiden) produce solo partizioni "piatte" (flat), ignorando queste relazioni gerarchiche.
• Limiti degli Algoritmi Esistenti:
  • I metodi basati sulla modularità (Louvain, Leiden) sono scalabili ma stocastici, sensibili agli iperparametri (es. parametro di risoluzione) e incapaci di restituire gerarchie.
  • I metodi basati sulla densità (come HDBSCAN*) sono ideali per forme di cluster irregolari e per la gestione del rumore, ma falliscono spesso su dati scRNA-seq ad alta dimensionalità, scartando un'alta percentuale di cellule come "rumore" a causa della perdita di informazione nelle distanze.

2. Metodologia: GraphHDBSCAN*

Gli autori propongono GraphHDBSCAN, un'estensione basata su grafi e priva di iperparametri (hyperparameter-free) di HDBSCAN, progettata specificamente per dati ad alta dimensionalità.

Componenti Chiave dell'Algoritmo:

1. Costruzione del Grafo di Similarità Strutturale Ponderata (WSS):

   • Invece di operare direttamente sulle distanze nello spazio delle feature, il metodo costruisce un grafo k-NN (k-Nearest Neighbors) dai dati tabulari (es. espressione genica).
   • Deriva un grafo di Similarità Strutturale Ponderata (Weighted Structural Similarity - WSS). Questo estende il concetto di "Shared Nearest Neighbors" (SNN) incorporando pesi sugli archi che rappresentano la forza della similarità tra i nodi.
   • Questo passaggio permette di operare senza necessitare di una riduzione della dimensionalità preliminare (come PCA, t-SNE o UMAP), preservando la struttura originale dei dati.
   • Le similarità vengono trasformate in dissimilarità ($d = 1 - sim$) per essere compatibili con i concetti di HDBSCAN*.

2. Clustering Gerarchico Densità-Based su Grafo:

   • L'algoritmo applica HDBSCAN* direttamente sul grafo WSS.
   • Utilizza il framework CORE-SG (Core-Spanning Graph) per calcolare efficientemente alberi di copertura minima (MST) multipli per un intervallo di valori del parametro di densità minPts. Questo rende l'algoritmo praticamente privo di iperparametri per l'esplorazione della gerarchia, generando una famiglia di gerarchie invece di una singola.

3. Estrazione di Partizioni Piatte (Flat Partitioning):

   • Per ottenere una partizione piatta dai risultati gerarchici, viene utilizzato il framework FOSC (Framework for Optimal Selection of Clusters), basato sul criterio di "Excess of Mass" (EOM). Questo seleziona i cluster che persistono su un ampio intervallo di livelli di densità, garantendo stabilità.

4. Propagazione delle Etichette per il Rumore (Label Propagation):

   • In scRNA-seq, scartare le cellule come "rumore" può essere problematico. GraphHDBSCAN* utilizza una strategia semi-supervisionata (HDBSCAN(cd,–)*) per assegnare le cellule inizialmente identificate come rumore ai cluster più vicini in base alla densità, utilizzando l'MST calcolato. Questo permette di ottenere una partizione completa senza perdere dati.

3. Contributi Chiave

• Integrazione di Struttura e Densità: Unisce la robustezza strutturale dei grafi (SNN/WSS) con la flessibilità della densità di HDBSCAN*, superando i limiti della distanza euclidea in spazi ad alta dimensionalità.
• Output Gerarchico Interpretabile: Fornisce una gerarchia densità-based che visualizza come le popolazioni cellulari si dividono e si fondono a diversi livelli di granularità, senza bisogno di tecniche di riduzione dimensionale ausiliarie per la visualizzazione.
• Gestione Avanzata del Rumore: Introduce un meccanismo di propagazione delle etichette che recupera le cellule "rumore", assegnandole ai cluster più appropriati, migliorando l'utilità pratica per l'analisi downstream.
• Efficienza Computazionale: Grazie a CORE-SG, il metodo calcola efficientemente intere famiglie di gerarchie con un costo computazionale aggiuntivo minimo rispetto a una singola esecuzione.

4. Risultati

Gli autori hanno valutato GraphHDBSCAN* su diversi dataset scRNA-seq (inclusi dati PBMC, CITE-seq e dataset di sviluppo embrionale) confrontandolo con HDBSCAN*, Louvain e Leiden.

• Ricostruzione Biologica: Il metodo ha recuperato con successo gerarchie biologiche significative, allineandosi alle ontologie cellulari note (es. differenziazione dei monociti, linfociti T e NK). Ha identificato sottopopolazioni fini non descritte in studi precedenti (es. sottotipi di monociti non classici).
• Performance di Partizione Piatte: Nonostante sia nato come metodo gerarchico, le partizioni piatte estratte da GraphHDBSCAN* hanno ottenuto punteggi ARI (Adjusted Rand Index) e AMI (Adjusted Mutual Information) superiori o competitivi rispetto a Louvain e Leiden su molti dataset.
• Robustezza: Il metodo mostra una variabilità inferiore rispetto a Louvain/Leiden ed è meno sensibile alla scelta degli iperparametri di default.
• Scalabilità: I test di runtime mostrano che GraphHDBSCAN* scala in modo fluido con l'aumento del numero di cellule, con un overhead computazionale accettabile rispetto ai metodi di partizione piatta pura, giustificato dal valore aggiunto della gerarchia.

5. Significato e Impatto

GraphHDBSCAN* rappresenta un avanzamento significativo nell'analisi computazionale dello scRNA-seq:

• Superamento del Compromesso: Risolve il compromesso tra la necessità di partizioni piatte (per l'annotazione standard) e la necessità di comprendere la gerarchia biologica (per la biologia dei sistemi).
• Indipendenza dalla Riduzione Dimensionale: Offre un approccio che può funzionare direttamente sui grafi di similarità derivati dai dati grezzi, riducendo il rischio di distorsione della struttura dei dati introdotto da tecniche come UMAP o t-SNE prima del clustering.
• Strumento Pratico: La capacità di recuperare le cellule "rumore" e di fornire gerarchie interpretabili lo rende uno strumento potente per la scoperta di nuovi sottotipi cellulari e per la validazione di stati cellulari transitori o rari.

In sintesi, il paper introduce un metodo che combina la teoria dei grafi e il clustering basato sulla densità per affrontare le specifiche sfide dei dati genomici moderni, offrendo risultati biologicamente più ricchi e computazionalmente robusti rispetto allo stato dell'arte.