A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

Ogni essere vivente porta con sé una storia scritta nel proprio DNA, un registro molecolare di come le popolazioni si siano spostate, mescolate e separate nel corso di migliaia di anni. Per gli scienziati, ricostruire questa storia è come cercare di assemblare un enorme puzzle frammentato dove i pezzi sono le variazioni genetiche e l'immagine è l'albero genealogico di una specie. Uno dei modi più affidabili per tracciare la discendenza umana è osservando il cromosoma Y, un piccolo pezzo di DNA trasmesso quasi invariato da padre a figlio. Poiché non si mescola con il DNA della madre, il cromosoma Y funge da linea di discendenza chiara e ininterrotta, permettendo ai ricercatori di mappare le profonde ramificazioni dell'albero genealogico umano. Tuttavia, man mano che la quantità di dati genetici cresce, il compito di trovare la corretta struttura dell'albero diventa incredibilmente difficile. Il numero di modi possibili per disporre anche un numero modesto di persone in un albero genealogico è così vasto da superare la capacità dei computer standard di controllare ogni possibilità una per una. Questa esplosione combinatoria ha costretto gli scienziati a fare affidamento su scorciatoie, o euristiche, che ipotizzano la risposta migliore rapidamente ma non garantiscono che sia quella vera.

Un team di ricercatori presso il CRS4 in Sardegna ha sviluppato un nuovo flusso di lavoro computazionale che affronta questo problema combinando due strategie distinte: scomporre un problema gigante in pezzi più piccoli e gestibili e utilizzare un tipo specializzato di algoritmo di ispirazione quantistica per risolvere tali pezzi. Il loro lavoro si concentra sui dati del cromosoma Y umano, concentrandosi in particolare sui cambiamenti a singola lettera nel codice genetico noti come polimorfismi a singolo nucleotide. I ricercatori sono partiti da un set di dati contenente informazioni genetiche da 150 campioni, che hanno ripulito rimuovendo 72 campioni non informativi privi dei necessari varianti genetici, lasciando 78 popolazioni maschili per l'analisi. Hanno poi utilizzato il loro nuovo metodo per ricostruire l'albero evolutivo. Invece di cercare di risolvere l'intero albero in una volta sola, il che sarebbe troppo complesso per la tecnologia attuale, hanno suddiviso il compito in due decisioni principali. Primo, hanno determinato quali gruppi di persone dovessero essere raggruppati insieme nell'albero. Secondo, hanno individuato dove dovesse essere posizionato l'inizio dell'albero, la radice, per mostrare la direzione del tempo.

Per prendere queste decisioni, i ricercatori hanno tradotto il problema biologico in un formato matematico noto come problema di ottimizzazione binaria quadratica non vincolata. In termini semplici, questo è un modo per trasformare la ricerca del miglior albero nella ricerca del punto più basso in un complesso paesaggio di colline e valli, dove il punto più basso rappresenta la storia familiare più probabile. La sfida è che questo paesaggio è troppo vasto per essere esplorato tutto in una volta. La soluzione del team è stata l'utilizzo di una tecnica chiamata decomposizione ADMM, che divide il vasto paesaggio in sezioni più piccole e sovrapposte. Ogni sezione viene risolta indipendentemente e poi i risultati vengono ricomposti per formare un insieme coerente. Ciò consente al sistema di gestire un problema di dimensioni che altrimenti sarebbero impossibili da elaborare per un singolo computer.

Per risolvere queste sezioni più piccole, il team ha impiegato un metodo chiamato ottimizzazione quantistica contro-diabatica digitalizzata. Questo approccio utilizza i principi della meccanica quantistica per trovare il punto più basso nel paesaggio molto rapidamente. A differenza di altri metodi quantistici che richiedono un processo lento e iterativo di tentativi ed errori, questa tecnica calcola il percorso verso la soluzione in un unico passaggio diretto. I ricercori hanno testato il loro flusso di lavoro su una simulazione computerizzata priva di rumore che imita il comportamento di un processore quantistico. Hanno scoperto che il metodo ha ricostruito con successo l'albero genealogico delle 78 popolazioni. L'albero risultante ha posizionato la radice in profondità all'interno delle linee di discendenza africane, una scoperta che si allinea con la comprensione scientifica consolidata delle origini umane. Inoltre, sebbene ogni raggruppamento identificato dal loro nuovo metodo fosse coerente con una tecnica di costruzione dell'albero standard e ampiamente accettata chiamata Neighbor-Joining, il nuovo metodo ha recuperato solo il 40% dei raggruppamenti trovati nell'albero di riferimento Neighbor-Joining, indicando che, sebbene il loro approccio sia preciso, ha identificato meno cluster totali rispetto al metodo standard.

Lo studio dimostra che questo approccio ibrido, che combina la suddivisione di grandi problemi con risolutori efficienti di tipo quantistico, è una via percorribile per la genomica delle popolazioni. Offre un modo per andare oltre l'incertezza delle scorciatoie tradizionali senza richiedere l'hardware massiccio e soggetto a errori dei computer quantistici a scala completa attualmente disponibili. Dimostrando di poter risolvere questi difficili problemi di ricostruzione dell'albero su un dispositivo quantistico simulato, i ricercatori hanno mostrato che la tecnologia è pronta per essere applicata a set di dati ancora più ampi in futuro. Il loro lavoro fornisce una pipeline chiara e passo dopo passo che prende i dati genetici grezzi e li trasforma in un albero genealogico radicato e annotato, completo dei marcatori genetici specifici che definiscono ogni ramo. Questo traguardo suggerisce che il campo si sta muovendo verso un futuro in cui l'intera complessità della storia evolutiva umana può essere mappata con maggiore precisione e minore dipendenza dalle approssimazioni.