A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

Elk levend wezen draagt een geschiedenis in zich die geschreven staat in zijn DNA, een moleculair verslag van hoe populaties zich gedurende duizenden jaren hebben verplaatst, vermengd en gescheiden. Voor wetenschappers is het reconstrueren van deze geschiedenis als het proberen te leggen van een enorme, gefragmenteerde puzzel waarbij de stukjes genetische variaties zijn en het plaatje de stamboom van een soort. Een van de meest betrouwbare manieren om de menselijke afstamming te traceren, is door naar het Y-chromosoom te kijken, een klein stukje DNA dat bijna onveranderd van vader op zoon wordt doorgegeven. Omdat het niet mengt met DNA van de moeder, fungeert het Y-chromosoom als een duidelijke, ononderbroken lijn van afstammeling, waardoor onderzoekers de diepe takken van de menselijke stamboom in kaart kunnen brengen. Echter, naarmate de hoeveelheid genetische gegevens groeit, wordt de taak om de juiste boomstructuur te vinden ongelooflijk moeilijk. Het aantal mogelijke manieren om zelfs een bescheiden aantal mensen in een stamboom te ordenen is zo groot dat het de capaciteit van standaardcomputers overstijgt om elke mogelijkheid één voor één te controleren. Deze combinatorische explosie heeft wetenschappers gedwongen om te vertrouwen op afkortingen, of heuristieken, die snel het beste antwoord raden maar niet garanderen dat dit het ware antwoord is.

Een team van onderzoekers bij CRS4 in Sardinië heeft een nieuwe computationele workflow ontwikkeld die dit probleem aanpakt door twee verschillende strategieën te combineren: het opdelen van een gigantisch probleem in kleinere, beheersbare stukken en het gebruik van een gespecialiseerd type quantum-geïnspireerd algoritme om die stukken op te lossen. Hun werk richt zich op menselijke Y-chromosoomdata, specifiek kijkend naar enkelvoudige letterveranderingen in de genetische code, bekend als single nucleotide polymorphisms. De onderzoekers begonnen met een dataset die genetische informatie bevatte van 150 monsters, die zij opschoonde door 72 niet-informatieve monsters te verwijderen die onnodige genetische varianten misten, waardoor er 78 mannelijke populaties overbleven voor analyse. Vervolgens gebruikten ze hun nieuwe methode om de evolutionaire boom te reconstrueren. In plaats van te proberen de gehele boom in één keer op te lossen, wat te complex zou zijn voor de huidige technologie, deelden ze de taak op in twee hoofdbeslissingen. Ten eerste bepaalden ze welke groepen mensen samen gegroepeerd moesten worden in de boom. Ten tweede bepaalden ze waar het absolute begin van de boom, de wortel, geplaatst moest worden om de richting van de tijd aan te geven.

Om deze beslissingen te nemen, vertaalden de onderzoekers het biologische probleem naar een wiskundig format dat bekend staat als een quadratic unconstrained binary optimization problem. In gewone taal is dit een manier om de zoektocht naar de beste boom te veranderen in een spel van het vinden van het laagste punt in een complex landschap van heuvels en dalen, waarbij het laagste punt de meest waarschijnlijke familiegeschiedenis vertegenwoordigt. De uitdaging is dat dit landschap te groot is om in één keer te verkennen. De oplossing van het team was het gebruik van een techniek genaamd ADMM-decompositie, die het enorme landschap opdeelt in overlappende kleinere secties. Elke sectie wordt onafhankelijk opgelost, waarna de resultaten weer aan elkaar worden gevoegd om een consistent geheel te vormen. Dit stelt het systeem in staat om een probleemomvang aan te pakken die anders onmogelijk te verwerken zou zijn voor een enkele computer.

Voor het oplossen van deze kleinere secties gebruikten het team een methode genaamd digitized counter-diabatic quantum optimization. Deze benadering maakt gebruik van de principes van de kwantummechanica om zeer snel het laagste punt in het landschap te vinden. In tegen tegenstelling tot andere kwantummethoden die een traag, iteratief proces van trial-and-error vereisen, berekent deze techniek het pad naar de oplossing in één directe passage. De onderzoekers testten hun workflow op een ruisvrije computersimulatie die het gedrag van een quantumprocessor nabootst. Ze ontdekten dat de methode erin slaagde de stamboom van de 78 populaties te reconstrueren. De resulterende boom plaatste de wortel diep binnen Afrikaanse lineages, een bevinding die overeenkomt met de gevestigde wetenschappelijke kennis over de menselijke oorsprong. Bovendien, hoewel elke groepering die door hun nieuwe methode werd geïdentificeerd consistent was met een standaard, algemeen aanvaarde boombouwtechniek genaamd Neighbor-Joining, herstelde de nieuwe methode slechts 40% van de groeperingen die door de Neighbor-Joining referentietree werden gevonden, wat aangeeft dat hoewel hun benadering precies is, zij minder totale clusters identificeerde dan de standaardmethode.

De studie toont aan dat deze hybride benadering, die het splitsen van grote problemen combineert met efficiënte quantum-achtige solvers, een levensvatbaar pad vooruit is voor de populatiegenomica. Het biedt een manier om voorbij de gokwerk van traditionele afkortingen te gaan zonder dat daarvoor de enorme, foutgevoelige hardware nodig is die volledige quantumcomputers momenteel vereisen. Door te bewijzen dat ze deze moeilijke boomreconstructieproblemen op een gesimuleerd quantumapparaat kunnen oplossen, hebben de onderzoekers aangetoond dat de technologie klaar is om in de toekomst zelfs op grotere datasets te worden toegepast. Hun werk biedt een duidelijke, stap-voor-stap pijplijn die ruwe genetische data neemt en deze verandert in een gewortelde, geannoteerde stamboom, compleet met de specifieke genetische markers die elke tak definiëren. Deze prestatie suggereert dat het veld beweegt naar een toekomst waarin de volledige complexiteit van de menselijke evolutiegeschiedenis met grotere precisie en minder afhankelijkheid van benadering in kaart kan worden gebracht.