Identifying Robust Subclonal Structures through Tumor Progression Tree Alignment

Deze paper introduceert omlta, een NP-moeilijk algoritme en de eerste computationele tool voor het bepalen van de optimale uitlijning van kloonbomen door het verwijderen van een minimaal aantal mutatielabels, welke is toegepast op data van de TRACERx-studie en melanoom-single-cell-data om robuuste subclonale structuren te identificeren.

De kern

Titel: Het vinden van de waarheid in de chaotische familiegeschiedenis van kanker

Stel je voor dat kanker een enorme, ingewikkelde familiegeschiedenis is. In plaats van mensen, zijn het cellen. Een gezonde cel deelt zich en wordt een tumor. Maar niet alle cellen in die tumor zijn hetzelfde. Sommige hebben een kleine mutatie (een "foutje" in hun DNA) gekregen, andere hebben er twee, en weer anderen hebben er drie. Ze vormen een stamboom: de oorspronkelijke cel is de grootouder, en de verschillende groepen cellen zijn de kinderen, kleinkinderen en achterkleinkinderen.

In de wetenschap noemen we deze stambomen clonale bomen. Ze vertellen ons hoe de kanker is gegroeid. Het probleem is echter dat wetenschappers verschillende manieren hebben om deze bomen te tekenen. Het is alsof je drie verschillende genealogen vraagt om dezelfde familiegeschiedenis te reconstrueren op basis van oude brieven. De ene genealoog tekent een boom met veel takken, de andere tekent er een met minder takken, en ze plaatsen soms dezelfde persoon op een andere plek.

Het probleem: Wie heeft gelijk?
Als twee wetenschappers twee verschillende bomen tekenen voor dezelfde tumor, hoe weten we dan welke delen van de boom betrouwbaar zijn? Welke mutaties zijn echt belangrijk en welke zijn misschien een fout in de berekening?

De oplossing: OMLTA (De "Perfecte Match"-machine)
De auteurs van dit paper hebben een nieuwe tool bedacht, genaamd OMLTA. Je kunt dit zien als een super-slimme "vergelijkingsmachine" voor deze kanker-stambomen.

Stel je voor dat je twee verschillende versies van dezelfde familiegeschiedenis hebt, maar ze zijn geschreven in een andere taal of met verschillende namen. OMLTA kijkt naar beide bomen en zegt: "Oké, laten we kijken wat ze gemeen hebben."

De machine doet twee dingen:

1. Het verwijdert de ruis: Het haalt de mutaties (de "namen" in de stamboom) weg die in de ene boom wel staan en in de andere niet, of die op een heel andere plek staan.
2. Het bouwt de "Waarheidsboom": Het houdt alleen de delen over die in beide bomen exact hetzelfde zijn. Het resultaat is een nieuwe, kleinere boom die we met 100% zekerheid kunnen zeggen: "Dit is de structuur die beide methoden bevestigen."

Een creatieve analogie: Het puzzel-voorbeeld
Stel je voor dat je twee grote legpuzzels hebt die dezelfde afbeelding moeten vormen (de tumor), maar ze zijn gemaakt door twee verschillende mensen.

• Puzzel A heeft een stukje blauw in de hoek dat er niet zou moeten zijn.
• Puzzel B mist dat blauwe stukje, maar heeft een extra rood stukje dat in Puzzel A ontbreekt.
• Soms zijn de stukjes in Puzzel A net iets anders geplaatst dan in Puzzel B.

OMLTA is als een slimme robot die de puzzels op de grond legt. Hij pakt alle stukjes die niet overeenkomen (het blauwe en het rode) en gooit ze weg. Wat overblijft, is de perfecte, overlappende kern van de puzzel. Die kern is de robuste waarheid. Alles wat overblijft, is iets waar beide puzzelbouwers het over eens zijn.

Waarom is dit belangrijk?
In de kankerwereld is het cruciaal om te weten welke mutaties echt belangrijk zijn.

• Als een mutatie in de "Waarheidsboom" (de overlap) staat, weten we dat deze mutatie echt bestaat en belangrijk is voor de groei van de kanker.
• Als een mutatie alleen in de ene boom staat en niet in de andere, is het misschien een foutje of een onzekerheid. We kunnen er dan minder zeker van zijn.

De auteurs hebben deze tool getest op echte kankerpatiënten (longkanker) en op laboratoriummuisjes (melanoom). Ze ontdekten interessante dingen:

• Bij sommige soorten kanker (zoals longkanker) waren de bomen van verschillende methodes heel erg verschillend. Dit betekent dat we bij die soorten kanker extra voorzichtig moeten zijn met onze conclusies.
• Ze zagen ook dat hoe meer "verwarrende" mutaties er waren (mutaties die maar in een klein deel van de cellen zaten), hoe moeilijker het was om de juiste boom te tekenen.
• Maar met OMLTA konden ze toch de "harde kern" van de waarheid vinden, zelfs als de oorspronkelijke bomen heel anders leken.

Samenvattend
Dit paper introduceert een slimme manier om de chaos van kanker-groei te doorgronden. In plaats van te twijfelen aan welke computerprogramma's de beste stamboom tekenen, gebruiken we OMLTA om te kijken wat ze allemaal gemeen hebben. Het is alsof we een vergrootglas gebruiken om de delen van de waarheid te vinden die niet verdwijnen, ongeacht hoe we naar de data kijken. Dit helpt artsen om betere beslissingen te nemen over behandelingen, gebaseerd op feiten die niemand kan ontkennen.

Technische samenvatting

Probleemstelling

In de kankergenomica is het begrijpen en vergelijken van de evolutionaire geschiedenis van tumoren fundamenteel. Tumoren worden gemodelleerd als klonale bomen (clonal trees), waarbij elke knoop een subkloon vertegenwoordigt die is gelabeld met een unieke set mutaties. Een groot probleem in dit veld is dat verschillende inferentiemethoden (zoals CONIPHER en PairTree) of verschillende sequencing-technieken (bulk vs. single-cell) vaak verschillende klonale bomen opleveren voor dezelfde tumordata.

Bestaande methoden om deze bomen te vergelijken (zoals consensus-bomen of andere afstandsmaatstaven) hebben beperkingen:

• Ze kunnen de precieze topologische overeenkomsten en verschillen niet kwantificeren zonder informatie te verliezen.
• Ze behandelen vaak alleen bladeren of tellen enkel ouder-kind-relaties, wat de complexe structuur van mutatie-labels in de bomen negeert.
• Er was tot nu toe geen computergestuurde tool om de optimale uitlijning tussen twee klonale bomen te vinden, waarbij het minimum aantal mutaties wordt verwijderd om isomorfie te bereiken.

Het doel van dit werk is het definiëren en oplossen van het Optimale Multi-Label Tree Alignment (omlta) probleem. Dit omvat het vinden van de minimale set mutatie-labels die uit twee bomen moeten worden verwijderd (en het toestaan van gratis knoop-expansies) zodat de resterende bomen isomorf zijn.

Methodologie

De auteurs introduceren omlta (Optimal Multi-Label Tree Alignment) en omltd (Optimal Multi-Label Tree Edit Distance).

1. Definitie van het probleem:

   • Gegeven twee klonale bomen $T_1$ en $T_2$.
   • Toegestane bewerkingen:
     • Label-deletie: Verwijder een mutatie-label (kost 1 eenheid).
     • Knoop-deletie: Verwijder een lege knoop (kost 0 eenheden).
     • Expansie: Verdeel de labels van een knoop over een lineaire keten van nieuwe knopen (kost 0 eenheden). Dit is cruciaal om verschillen in resolutie tussen bulk- en single-cell data te reconciliëren.
   • Doel: Vind een reeks bewerkingen met minimale kosten (aantal verwijderde labels) zodat de resulterende bomen isomorf zijn.

2. Complexiteit:

   • Het berekenen van omlta/omltd is NP-hard.
   • De auteurs tonen aan dat het probleem Fixed Parameter Tractable (FPT) is, waarbij de parameter $k$ het optimale aantal te verwijderen labels is.

3. Het Algorithm:

   • De auteurs ontwikkelen een recursief algoritme gebaseerd op dynamisch programmeren.
   • De kern van het algoritme is het iteratief kiezen van een label in de wortel van een boom en beslissen of dit label moet worden gematcht (door expansie en verwijderen van bovenliggende knopen in de andere boom) of verwijderd.
   • Tijdscomplexiteit: Het algoritme heeft een looptijd van $O(2^{k/2} \cdot L^3 \log L)$, waarbij $L$ het totale aantal unieke mutatie-labels is en $k$ de optimale edit-afstand.
   • De exponentiële term $2^{k/2}$ is strikt beter dan de $2.62^k$ van de state-of-the-art algoritmen voor ongelabelde boom-edit-afstand. Omdat $k$ in de praktijk vaak klein is ten opzichte van $L$, is het algoritme efficiënt toepasbaar.

4. Implementatie:

   • De tool is open source beschikbaar op GitHub (https://github.com/algo-cancer/omlta).

Belangrijkste Resultaten

De auteurs hebben omlta toegepast op twee grote datasets:

1. TRACERx Cohort (Non-Small Cell Lung Cancer - NSCLC):

• Dataset: 126 metastatische NSCLC-tumoren.
• Vergelijking: Bomen geïnfereerd door CONIPHER (de standaardmethode in TRACERx) versus PairTree.
• Vindst:
  • Er is aanzienlijke variatie in de topologie tussen de methoden. CONIPHER-produceert vaak meer onbalans (diepere bomen) dan PairTree.
  • Subtype Verschil: LUAD (Longklierkanker) cases tonen een hogere discordantie (hogere omltd) dan LUSC (Longplaveiselcelkanker).
  • Correlatie: Er is een sterke negatieve correlatie tussen de gemiddelde Cancer Cell Fraction (CCF) en de discordantie. Tumoren met lagere CCF (meer subclonale mutaties) zijn minder robuust ten opzichte van de keuze van de inferentiemethode.
  • Biologische Implicatie: Mutaties in genen met een "rol in kanker" (oncogenen/tumorsuppressoren) bleken vaker discordant te worden geplaatst dan verwacht, wat de robuustheid van afgeleide biologische conclusies (zoals timing van metastase) in gevaar brengt.

2. B2905 Melanoma Preklinisch Model:

• Dataset: Single-cell en bulk sequencing data van een muismodel voor melanoom.
• Vergelijking:
  • Bulk data (WES vs. WTS): De bomen waren zeer vergelijkbaar, met een lage omltd, wat aangeeft dat bulk data robuuste structuren kan vastleggen.
  • Single-cell data (Smart-seq2 vs. Seq-Well, en Behandeld vs. Controle): De omltd-waarden waren hier veel hoger (tot 2/3 van de labels moest worden verwijderd) vanwege sampling-variabiliteit en data-schaarste.
  • Desondanks slaagde omlta erin om robuuste substructuren (lineages) te identificeren die consistent waren tussen de datasets, wat nuttig is voor het bestuderen van immuno-editing.

Significantie en Bijdragen

1. Eerste Tool voor Klonale Boom-uitlijning: Dit is de eerste computergestuurde methode die de optimale uitlijning tussen twee klonale bomen berekent, in plaats van alleen een consensusboom te genereren.
2. Robuuste Biologische Inference: Door de gemeenschappelijke substructuren (de "alignment tree") te isoleren, kunnen onderzoekers robuuster conclusies trekken over tumorprogressie, ongeacht de gebruikte inferentiemethode of sequencing-technologie.
3. FPT Algoritme: Het bieden van een efficiënt algoritme voor een NP-hard probleem, specifiek geoptimaliseerd voor de eigenschappen van kankerdata (waar $k$ vaak klein is).
4. Validatie van Inferentiemethoden: De tool biedt een kwantitatieve manier om nieuwe inferentiemethoden te valideren tegen bestaande standaarden door hun overeenkomst te meten.
5. Klinische Relevantie: De resultaten tonen aan dat voor tumoren met veel subclonale mutaties (lage CCF), de keuze van de inferentiemethode de interpretatie van metastase-timing en subkloon-structuur sterk kan beïnvloeden. Dit onderstreept de noodzaak van robuuste uitlijningstechnieken voor nauwkeurige therapie-ontwikkeling.

Kortom, dit paper levert een wiskundig onderbouwd en praktisch toepasbaar raamwerk om de onzekerheid in tumor-evolutiemodellen te kwantificeren en de meest betrouwbare evolutionaire patronen te extraheren.