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

Dit paper introduceert GraphHDBSCAN*, een hyperparameter-vrije, grafgebaseerde hiërarchische clusteringmethode voor single-cell RNA-sequencing-data die zowel robuuste hiërarchische relaties als hoogwaardige vlakke partities kan onthullen, waardoor deze de bestaande methoden overtreft.

De kern

GraphHDBSCAN: Een slimme manier om cellen te sorteren*

Stel je voor dat je een enorme berg met miljoenen verschillende soorten knikkers hebt. Elke knikker vertegenwoordigt één enkele cel uit een menselijk lichaam. Je wilt deze knikkers sorteren in groepjes: welke zijn rode bloedcellen, welke zijn witte bloedcellen, en welke zijn misschien een heel zeldzaam type dat nog nooit eerder is gezien?

Dit is precies wat wetenschappers doen met scRNA-seq (single-cell RNA sequencing). Ze kijken naar de "identiteitskaart" (het DNA-actieve gedeelte) van miljoenen cellen tegelijk. Maar hier zit het probleem: de data is zo complex, zo rommelig en zo groot, dat het sorteren ervan als een nachtmerrie is voor computers.

Deze paper introduceert een nieuwe, slimme methode genaamd GraphHDBSCAN*. Laten we uitleggen hoe dit werkt met een paar simpele vergelijkingen.

1. Het oude probleem: De "Vlakke" Kaart

Tot nu toe gebruikten wetenschappers methoden die werken als een flat map (een platte kaart). Ze zeggen: "Oké, deze 1000 cellen horen bij groep A, en die 500 bij groep B."

• Het nadeel: Dit negeert de familiebanden. In de biologie zijn cellen vaak familie. Een "witte bloedcel" is een grote familie, maar daarbinnen zitten sub-families (zoals monocyten die weer in drie soorten kunnen vallen). Een platte kaart ziet alleen de hoofdgroepen en mist de fijne details.
• De hyperparameters: De oude methoden waren ook lastig. Je moest een knop draaien (een instelling) om te zeggen: "Hoe groot moeten de groepen zijn?" Draai je te ver, en je krijgt één grote brij. Draai je te weinig, en je hebt duizenden kleine groepjes. Het was een gok.

2. De nieuwe oplossing: De "3D-Boom"

GraphHDBSCAN* doet iets anders. In plaats van een platte kaart, bouwt het een 3D-familieboom.

• De Boom: Stel je een boom voor. Bovenaan heb je de stam (alle cellen). Naarmate je naar beneden kijkt, vertakt de boom zich. Eerst splitsen de cellen in grote takken (bijvoorbeeld: "Immuuncellen" vs. "Niet-Immuuncellen"). Dan splitsen die takken weer in kleinere takken (bijvoorbeeld: "T-cellen" vs. "B-cellen"), en uiteindelijk in de kleinste twijgjes (specifieke subtypes).
• Het voordeel: Je kunt nu zien hoe cellen met elkaar verwant zijn. Je ziet niet alleen wie er bij elkaar hoort, maar ook hoe ze zich hebben ontwikkeld.

3. Hoe werkt het? (De "Vrienden van Vrienden"-truc)

De grootste uitdaging bij deze data is dat het zo "dicht" is (veel dimensies). Het is alsof je probeert vrienden te vinden in een kamer waar iedereen tegelijkertijd schreeuwt. De afstand tussen twee mensen zegt dan niets meer over of ze vrienden zijn.

GraphHDBSCAN* gebruikt een slimme truc: De "Vrienden van Vrienden"-methode.

• In plaats van te kijken naar hoe ver twee cellen van elkaar af staan (wat in deze rommelige data niets zegt), kijkt het naar: "Hebben deze twee cellen dezelfde vrienden?"
• Als cel A en cel B allebei dezelfde 5 andere cellen als "buurman" hebben, dan zijn ze waarschijnlijk familie, zelfs als ze op het eerste gezicht ver uit elkaar lijken.
• De methode bouwt een netwerk (een grafiek) van deze vriendenrelaties. Daarna zoekt het in dit netwerk naar dichte groepjes.

4. Geen gissen meer: De "Zelfwerkende" Boom

Een van de coolste dingen is dat de methode geen knoppen nodig heeft om te draaien.

• Oude methoden: "Hoe groot moet mijn groep zijn?" (Je moet raden).
• GraphHDBSCAN*: "Kijk maar naar de boom." De computer bouwt de hele boom op. Jij kunt erdoorheen lopen en op elk niveau stoppen waar jij het interessant vindt. Je ziet automatisch waar de grote groepen zitten en waar de kleine, zeldzame groepen zich verstoppen. Het is alsof je een zoomfunctie hebt die automatisch werkt.

5. Wat gebeurt er met de "vreemden"? (Ruis)

In elke dataset zijn er cellen die niet goed passen. Soms zijn het echte rare cellen, maar vaak zijn het gewoon "foutjes" in de meting (zoals een dubbelgevangen cel of een kapotte meting).

• Oude methoden: "Dit is ruis, gooi het weg." (Veel waardevolle data gaat verloren).
• GraphHDBSCAN*: "Wacht even, laten we kijken waar deze 'vreemden' het dichtst bij zitten." De methode gebruikt een slimme techniek om deze cellen toch een label te geven op basis van hun omgeving, zonder dat ze de groep verstoren. Het redt dus cellen die anders verloren zouden gaan.

Het resultaat in de praktijk

De auteurs hebben dit getest op echte bloedcel-data.

• Ze ontdekten nieuwe subtypes van monocyten (een type witte bloedcel) die eerder niet waren gezien.
• Ze konden de hele "stamboom" van het immuunsysteem reconstrueren, van de grote takken tot de kleinste twijgjes.
• Ze waren zelfs beter dan de huidige standaardmethoden (zoals Louvain en Leiden) in het vinden van de juiste groepen, en dat zonder dat je als gebruiker iets hoeft in te stellen.

Samenvatting

GraphHDBSCAN* is als een super-slimme, zelfwerkende sorteerrobot voor cellen.

1. Het kijkt niet naar afstand, maar naar gemeenschappelijke vrienden (netwerk).
2. Het maakt geen platte lijst, maar een familieboom (hiërarchie).
3. Het heeft geen instellingen nodig die je moet raden.
4. Het redt cellen die anders als "fout" zouden worden weggegooid.

Dit helpt artsen en biologen om de complexe wereld van onze cellen beter te begrijpen, wat essentieel is voor het vinden van nieuwe behandelingen voor ziektes.

Technische samenvatting

Hieronder volgt een gedetailleerde technische samenvatting van het artikel "GraphHDBSCAN: Graph-based Hierarchical Clustering on High Dimensional Single-cell RNA Sequencing Data"* in het Nederlands.

1. Het Probleem

Single-cell RNA-sequencing (scRNA-seq) is een revolutionaire technologie die het mogelijk maakt om de heterogeniteit van cellen op een ongekende schaal te bestuderen. Echter, het analyseren van deze data brengt grote computationele uitdagingen met zich mee:

• Kwaliteit van de data: scRNA-seq-datasets zijn extreem spaarzaam (sparse), hoogdimensionaal en ruisgevoelig. In hoge dimensies verliezen traditionele afstandsmaten hun informatieve waarde (de "curse of dimensionality"), wat de robuustheid van clusterformatie ondermijnt.
• Hiërarchische structuur: Biologische processen vertonen vaak een natuurlijke hiërarchie (bijv. brede celtypen splitsen zich in gespecialiseerde subtypen). Bestaande state-of-the-art methoden, zoals Louvain en Leiden (die gebaseerd zijn op modulaire optimalisatie), genereren meestal slechts een vlakke partitie (flat partition) en negeren deze hiërarchische relaties.
• Beperkingen van HDBSCAN*: Hoewel HDBSCAN* uitstekend is voor het detecteren van clusters met variërende dichtheid en ruis, presteert het slecht in hoge dimensies als het direct op afstandsmaten werkt. Dit leidt vaak tot het ten onrechte classificeren van een groot deel van de cellen als "ruis" (noise).
• Hyperparameter-gevoeligheid: Veel bestaande methoden zijn gevoelig voor hyperparameters (zoals de resolutieparameter bij Leiden), wat de reproduceerbaarheid en bruikbaarheid beperkt.

2. Methodologie: GraphHDBSCAN*

De auteurs introduceren GraphHDBSCAN*, een grafgebaseerde, dichtheidsgebaseerde hiërarchische clusteringmethode die specifiek is ontworpen voor grote, hoogdimensionale datasets zoals scRNA-seq. De kern van de methode is een verschuiving van directe afstandsberekening naar een grafrepresentatie.

Belangrijkste stappen in de pipeline:

1. Constructie van de WSS-graf (Weighted Structural Similarity):

   • In plaats van te werken met de oorspronkelijke feature-ruimte, bouwt de methode eerst een k-NN-graf (k-nearest neighbors) direct op de tabulaire data (na selectie van Highly Variable Genes).
   • Vervolgens wordt een Weighted Structural Similarity (WSS) graf afgeleid. Dit is een generalisatie van de "Shared Nearest Neighbor" (SNN) concepten. De randen in deze graf krijgen gewichten die de sterkte van de gelijkenis tussen knopen weergeven, gebaseerd op de overlap van hun buren.
   • Deze stap omzeilt de noodzaak voor voorafgaande dimensiereductie (zoals PCA of UMAP), wat vaak de oorspronkelijke dichtheidsstructuur vervormt.

2. Toepassing van HDBSCAN* op de Graf:

   • De WSS-gewichten worden omgezet in dissimilariteiten (afstanden).
   • HDBSCAN* wordt toegepast op deze graf. De kernafstanden en de "Mutual Reachability Distance" (MRD) worden berekend op basis van de grafstructuur in plaats van de volledige afstandsmatrix.
   • Dit maakt het mogelijk om clusters van variërende dichtheid te vinden en ruis te detecteren, zelfs in zeer hoge dimensies.

3. Efficiëntie via CORE-SG:

   • Om de methode hyperparameter-vrij te maken voor de gebruiker (wat betreft het aantal clusters en de dichtheidsniveaus), wordt gebruik gemaakt van CORE-SG (Core-distance based Spanning Graph).
   • CORE-SG stelt de algoritme in staat om meerdere hiërarchieën te berekenen voor een reeks minPts-waarden vanuit één enkele initiële run, zonder de MST (Minimum Spanning Tree) voor elke parameter opnieuw te hoeven berekenen. Dit verlaagt de computationele kosten aanzienlijk.

4. Flat Partitioning en Label Propagatie:

   • Flat Partitioning: Uit de gegenereerde hiërarchie wordt een vlakke partitie gehaald met behulp van het FOSC-kader (Framework for Optimal Selection of Clusters), dat clusters selecteert op basis van stabiliteit (Excess of Mass).
   • Label Propagatie voor Ruis: In scRNA-seq is het vaak onwenselijk om cellen als ruis te verwijderen. GraphHDBSCAN* gebruikt een semi-supervisie strategie (HDBSCAN*(cd,–)) om cellen die als ruis zijn gemarkeerd, opnieuw toe te wijzen aan de dichtstbijzijnde cluster via de MST. Dit gebeurt op basis van de intrinsieke dichtheidsstructuur, niet op basis van clustergrootte.

3. Belangrijkste Bijdragen

• Hiërarchisch inzicht: De methode levert een interpreteerbare, dichtheidsgebaseerde hiërarchie op die biologische relaties (zoals differentiatiepaden) zichtbaar maakt, in tegenstelling tot de vlakke output van Louvain/Leiden.
• Robuustheid in hoge dimensies: Door te werken op een WSS-graf in plaats van directe afstanden, overwint de methode de "curse of dimensionality" en reduceert het het aantal onterecht als ruis gemarkeerde cellen.
• Hyperparameter-vrij (in de praktijk): Dankzij CORE-SG kan de gebruiker de volledige familie van hiërarchieën verkennen zonder specifieke minPts-waarden te hoeven kiezen.
• Geavanceerde Ruisbehandeling: De geïntegreerde label-propagatiestrategie zorgt ervoor dat "ruis" cellen nuttige biologische informatie kunnen bevatten (bijv. overgangstoestanden) en deze correct worden toegewezen aan bestaande clusters.

4. Resultaten en Evaluatie

De auteurs hebben GraphHDBSCAN* getest op meerdere scRNA-seq-datasets (waaronder PBMC, CITE-seq en embryonale ontwikkeling datasets) en vergeleken met HDBSCAN*, Louvain en Leiden.

• Biologische Validatie:

  • De methode slaagde erin om bekende hiërarchieën van hematopoëse (bloedcelvorming) nauwkeurig te reconstrueren.
  • Het onthulde fijnmazige subpopulaties die in eerdere studies niet waren beschreven. Bijvoorbeeld, binnen monocyten werden twee nieuwe subgroepen geïdentificeerd die onderscheiden konden worden door specifieke eiwitmerkers (zoals CD11c).
  • De hiërarchieën kwamen overeen met de biologische "ground truth" (bekende differentiatiepaden).

• Kwantitatieve Prestaties (Flat Partitioning):

  • Hoewel GraphHDBSCAN* primair een hiërarchische methode is, presteerde de afgeleide vlakke partitie concurrerend of superieur aan Louvain en Leiden.
  • Op basis van Adjusted Rand Index (ARI) en Adjusted Mutual Information (AMI) scoorde GraphHDBSCAN* consistent hoger of gelijk aan de state-of-the-art methoden, met minder variabiliteit tussen datasets.
  • De oorspronkelijke HDBSCAN* (zonder graf-transformatie) presteerde aanzienlijk slechter, wat de noodzaak van de graf-benadering bevestigt.

• Efficiëntie:

  • De runtime-schaalbaarheid is lineair en praktisch bruikbaar, zelfs voor datasets met tienduizenden cellen. De overhead door het bouwen van de hiërarchie is klein vergeleken met de winst in analysecapaciteit.

5. Betekenis en Conclusie

GraphHDBSCAN* vertegenwoordigt een significante doorbraak in de analyse van single-cell data. Het combineert de sterkte van dichtheidsgebaseerde clustering (het kunnen vinden van clusters van verschillende vormen en dichtheden) met de schaalbaarheid en robuustheid van graf-methoden.

De belangrijkste implicaties zijn:

1. Biologisch inzicht: Het biedt onderzoekers een manier om de complexe hiërarchische organisatie van cellen direct te visualiseren en te analyseren, zonder afhankelijk te zijn van dimensiereductietechnieken die de data kunnen vervormen.
2. Betrouwbaarheid: Het reduceert de gevoeligheid voor hyperparameters en levert stabielere resultaten dan modulaire methoden.
3. Data-integriteit: Door ruis op een intelligente manier te herlabelen in plaats van te verwijderen, behoudt de methode waardevolle cellen die anders verloren zouden gaan, wat cruciaal is voor het bestuderen van zeldzame celtypen of overgangstoestanden.

Kortom, GraphHDBSCAN* vult een kritieke lacune in het scRNA-seq-toolbox door een methode te bieden die zowel de hiërarchische structuur als de fijnmazige details van complexe biologische data effectief kan ontrafelen.