A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

Chaque être vivant porte une histoire écrite dans son ADN, un enregistrement moléculaire de la manière dont les populations ont bougé, se sont mélangées et se sont séparées au cours de milliers d'années. Pour les scientifiques, reconstruire cette histoire revient à essayer d'assembler un puzzle massif et fragmenté où les pièces sont des variations génétiques et l'image est l'arbre généalogique d'une espèce. L'un des moyens les plus fiables de retracer l'ascendance humaine consiste à examiner le chromosome Y, un petit morceau d'ADN transmis presque inchangé de père en fils. Parce qu'il ne se mélange pas avec l'ADN de la mère, le chromosome Y agit comme une ligne de descendance claire et ininterrompue, permettant aux chercheurs de cartographier les branches profondes de l'arbre généalogique humain. Cependant, à mesure que la quantité de données génétiques augmente, la tâche consistant à trouver la structure correcte de l'arbre devient incroyablement difficile. Le nombre de façons possibles d'organiser même un nombre modeste de personnes en un arbre généalogique est si vaste qu'il dépasse la capacité des ordinateurs standards à vérifier chaque possibilité une par une. Cette explosion combinatoire a forcé les scientifiques à s'appuyer sur des raccourcis, ou heuristiques, qui devinent la meilleure réponse rapidement mais ne garantissent pas qu'elle soit la vraie.

Une équipe de chercheurs du CRS4 en Sardaigne a développé un nouveau flux de travail computationnel qui aborde ce problème en combinant deux stratégies distinctes : diviser un problème géant en morceaux plus petits et gérables, et utiliser un type spécialisé d'algorithme d'inspiration quantique pour résoudre ces morceaux. Leur travail se concentre sur les données du chromosome Y humain, en examinant spécifльно les changements d'une seule lettre dans le code génétique, connus sous le nom de polymorphismes nucléotidiques simples. Les chercheurs ont commencé avec un ensemble de données contenant des informations génétiques de 150 échantillons, qu'ils ont nettoyés pour éliminer 72 échantillons non informatifs dépourvus des variants génétiques nécessaires, laissant 78 populations masculines pour l'analyse. Ils ont ensuite utilisé leur nouvelle méthode pour reconstruire l'arbre évolutif. Au lieu d'essayer de résoudre l'arbre entier à la fois, ce qui serait trop complexe pour la technologie actuelle, ils ont divisé la tâche en deux décisions principales. Premièrement, ils ont déterminé quels groupes de personnes devaient être regroupés ensemble sur l'arbre. Deuxièmement, ils ont déterminé où le tout début de l'arbre, la racine, devait être placée pour montrer la direction du temps.

Pour prendre ces décisions, les chercheurs ont traduit le problème biologique en un format mathématique connu sous le nom de problème d'optimisation binaire quadratique non contraint. En termes simples, il s'agit de transformer la recherche du meilleur arbre en un jeu consistant à trouver le point le plus bas dans un paysage complexe de collines et de vallées, où le point le plus bas représente l'histoire familiale la plus probable. Le défi est que ce paysage est trop vaste pour être exploré entièrement d'un coup. La solution de l'équipe a été d'utiliser une technique appelée décomposition ADMM, qui divise le paysage massif en sections plus petites et chevauchantes. Chaque section est résolue indépendamment, puis les résultats sont recollés pour former un tout cohérent. Cela permet au système de gérer une taille de problème qui serait autrement impossible à traiter pour un seul ordinateur.

Pour résoudre ces sections plus petites, l'équipe a employé une méthode appelée optimisation quantique numérique contre-diabatique. Cette approche utilise les principes de la mécanique quantique pour trouver le point le plus bas du paysage très rapidement. Contraquirement à d'autres méthodes quantiques qui nécessitent un processus itératif lent de tâtonnements et d'erreurs, cette technique calcule le chemin vers la solution en une seule passe directe. Les chercheurs ont testé leur flux de travail sur une simulation informatique sans bruit qui imite le comportement d'un processeur quantique. Ils ont constaté que la méthode a réussi à reconstruire l'arbre généalogique des 78 populations. L'arbre résultant a placé la racine profondément au sein des lignées africines, une découverte qui s'aligne sur la compréhension scientifique établie des origines humaines. De plus, bien que chaque regroupement identifié par leur nouvelle méthode soit cohérent avec une technique de construction d'arbre standard et largement acceptée appelée "Neighbor-Joining", la nouvelle méthode n'a récupéré que 40 % des regroupements trouvés dans l'arbre de référence Neighbor-Joining, indiquant que bien que leur approche soit précise, elle a identifié moins de clusters totaux que la méthode standard.

L'étude démontre que cette approche hybride, qui combine la division de grands problèmes avec des solveurs de style quantique efficaces, est une voie viable pour la génomique des populations. Elle offre un moyen d'aller au-delà des conjectures des raccourcis traditionnels sans nécessiter le matériel massif et sujet aux erreurs que les ordinateurs quantiques à pleine échelle nécessitent actuellement. En prouvant qu'ils peuvent résoudre ces problèmes difficiles de reconstruction d'arbre sur un dispositif quantique simulé, les chercheurs ont montré que la technologie est prête à être appliquée à des ensembles de données encore plus vastes à l'avenir. Leur travail fournit un pipeline clair, étape par étape, qui prend les données génétiques brutes et les transforme en un arbre généalogique annoté et enraciné, complet avec les marqueurs génétiques spécifiques qui définissent chaque branche. Cette réussite suggère que le domaine se dirige vers un avenir où la pleine complexité de l'histoire évolutive humaine peut être cartographiée avec une plus grande précision et moins de dépendance à l'égard de l'approximation.