A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

Jedes Lebewesen trägt eine in seiner DNA geschriebene Geschichte in sich, ein molekulares Protokoll darüber, wie sich Populationen über Jahrtausende hinweg bewegt, vermischt und getrennt haben. Für Wissenschaftler gleicht die Rekonstruktion dieser Geschichte dem Versuch, ein riesiges, fragmentiertes Puzzle zusammenzusetzen, bei dem die Teile genetische Variationen sind und das Bild der Stammbaum einer Spezies ist. Eine der zuverlässigsten Methoden, um die menschliche Abstammung nachzuverfolgen, ist die Betrachtung des Y-Chromosoms, eines kleinen Stücks DNA, das fast unverändert vom Vater an den Sohn weitergegeben wird. Da es sich nicht mit der DNA der Mutter vermischt, fungiert das Y-Chromosom als klare, ungebrochene Abstammungslinie, die es Forschern ermöglicht, die tiefen Verzweigungen des menschlichen Stammbaums abzubilden. Doch mit der wachsenden Menge an genetischen Daten wird die Aufgabe, die korrekte Baumstruktur zu finden, unglaublich schwierig. Die Anzahl der möglichen Möglichkeiten, selbst eine bescheidene Anzahl von Menschen in einem Stammbaum anzuordnen, ist so gewaltig, dass sie die Kapazität herkömmlicher Computer übersteigt, jede Möglichkeit einzeln zu prüfen. Diese kombinatorische Explosion hat die Wissenschaftler dazu gezwungen, sich auf Abkürzungen, oder Heuristiken, zu verlassen, die zwar schnell die beste Antwort vermuten, aber nicht garantieren, dass es die wahre ist.

Ein Forschungsteam am CRS4 in Sardinien hat einen neuen computergestützten Workflow entwickelt, der dieses Problem angeht, indem er zwei unterschiedliche Strategien kombiniert: das Aufteilen eines riesigen Problems in kleinere, handhabbare Stücke und die Verwendung eines speziellen Typs von quanteninspiriertem Algorithmus zur Lösung dieser Stücke. Ihre Arbeit konzentriert sich auf menschliche Y-Chromosom-Daten, wobei sie speziell auf Einzelbuchstaben-Veränderungen im genetischen Code achten, die als Einzelnukleotid-Polymorphismen bekannt sind. Die Forscher begannen mit einem Datensatz, der genetische Informationen aus 150 Proben enthielt, und bereinigten diesen, um 72 nicht informative Proben zu entfernen, denen die notwendigen genetischen Varianten fehlten, wodurch 78 männliche Populationen für die Analyse übrig blieben. Sie nutzten dann ihre neue Methode, um den evolutionären Baum zu rekonstruieren. Anstatt zu versuchen, den gesamten Baum auf einmal zu lösen, was für die heutige Technologie zu komplex wäre, teilten sie die Aufgabe in zwei Hauptentscheidungen auf. Zuerwert bestimmten sie, welche Gruppen von Menschen im Baum zusammen gruppiert werden sollten. Zweitens ermittelten sie, wo der Ursprung des Baumes, die Wurzel, platziert werden sollte, um die Richtung der Zeit anzuzeigen.

Um diese Entscheidungen zu treffen, übersetzten die Forscher das biologische Problem in ein mathematisches Format, das als quadratisches, unbeschränktes binäres Optimierungsproblem bekannt ist. In einfachen Worten ausgedrückt, ist dies eine Art, die Suche nach dem besten Baum in ein Spiel der Suche nach dem tiefsten Punkt in einer komplexen Landschaft aus Hügeln und Tälern zu verwandeln, wobei der tiefste Punkt die wahrscheinlichste Familiengeschichte darstellt. Die Herausforderung besteht darin, dass diese Landschaft zu groß ist, um sie auf einmal zu erkunden. Die Lösung des Teams war der Einsatz einer Technik namens ADMM-Zerlegung, die die massive Landschaft in überlappende kleinere Abschnitte unterteilt. Jeder Abschnitt wird unabhängig gelöst, und anschließend werden die Ergebnisse wieder zusammengefügt, um ein konsistentes Ganzes zu bilden. Dies ermöglicht es dem System, eine Problemgröße zu bewältigen, die für einen einzelnen Computer sonst unmöglich zu verarbeiten wäre.

Für die Lösung dieser kleineren Abschnitte setzte das Team eine Methode namens digitalisierte counter-diabatische Quantenoptimierung ein. Dieser Ansatz nutzt die Prinzipien der Quantenmechanik, um den tiefsten Punkt in der Landschaft sehr schnell zu finden. Im Gegensatz zu anderen Quantenmethoden, die einen langsamen, iterativen Prozess von Versuch und Irrtum erfordern, berechnet diese Technik den Pfad zur Lösung in einem einzigen, direkten Durchgang. Die Forscher testeten ihren Workflow an einer rauschfreien Computersimulation, die das Verhalten eines Quantenprozessors nachahmt. Sie fanden heraus, dass die Methode den Stammbaum der 78 Populationen erfolgreich rekonstruierte. Der resultierende Baum platzierte die Wurzel tief innerhalb afrikanischer Abstammungslinien, ein Befund, der mit dem etablierten wissenschaftlichen Verständnis der menschlichen Ursprünge übereinstimmt. Darüber hinaus war jede durch ihre neue Methode identifizierte Gruppierung konsistent mit einer standardmäßigen, weithin akzeptierten Baumgestaltungstechnik namens Neighbor-Joining; dennoch stellte die neue Methode nur 40 % der Gruppierungen wieder her, die der Neighbor-Joining-Referenzbaum fand, was darauf hindeutet, dass ihr Ansatz zwar präzise ist, aber weniger Gesamtknoten identifizierte als die Standardmethode.

Die Studie zeigt, dass dieser hybride Ansatz, der das Aufteilen großer Probleme mit effizienten Quanten-ähnlichen Solvern kombiniert, ein gangbarer Weg für die Populationsgenomik ist. Er bietet eine Möglichkeit, über das Raten traditioneller Abkürzungen hinauszugehen, ohne die massiven, fehleranfälligen Hardware-Anforderungen vollskaliger Quantencomputer zu benötigen. Indem sie bewiesen haben, dass sie diese schwierigen Stammbaum-Rekonstruktionsprobleme auf einem simulierten Quantengerät lösen können, haben die Forscher gezeigt, dass die Technologie bereit ist, in Zukunft auch auf noch größere Datensätze angewendet zu werden. Ihre Arbeit liefert eine klare, schrittweise Pipeline, die rohe genetische Daten nimmt und sie in einen verwurzelten, annotierten Stammbaum verwandelt, lengkap mit den spezifischen genetischen Markern, die jeden Zweig definieren. Diese Errungenschaft deutet darauf hin, dass sich das Feld einer Zukunft nähert, in der die volle Komplexität der menschlichen Evolutionsgeschichte mit größerer Präzision und weniger Abhängigkeit von Annäherungen abgebildet werden kann.