Lossless Reductions and Hybrid Sampling for Phylogeny Using the Maximum Compatibility Criterion
Cet article améliore la reconstruction phylogénétique de compatibilité maximale en introduisant des réductions de graphes sans perte et des techniques d'échantillonnage hybrides quantiques-classiques pour énumérer efficacement tous les ensembles de caractères optimaux, démontrant leur efficacité sur les données du SARS-CoV-2 tout en abordant les limites des multiplicateurs de Lagrange traditionnels sur les dispositifs quantiques bruités.
Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). Ceci est une explication générée par l'IA d'un preprint qui n'a pas été évalué par des pairs. Ce n'est pas un avis médical. Ne prenez pas de décisions de santé basées sur ce contenu. Lire la clause de non-responsabilité complète
La vie sur Terre est une histoire écrite dans le code génétique de chaque être vivant, une histoire de la façon dont les populations se sont divisées, ont migré et ont changé au fil de millions d'années. Pour lire cette histoire, les scientifiques construisent des arbres généalogiques, appelés phylogénies, qui cartographient les relations entre différents organismes. Ces arbres ne sont pas de simples curiosités académiques ; ils aident les chercheurs à comprendre comment le cancer évolue au sein d'un seul corps, comment concevoir des médicaments ciblant des agents pathogènes spécifiques et comment suivre la propagation de nouveaux variants viraux comme le SARS-CoV-2. Cependant, reconstruire ces arbres est difficile car nous ne possédons que les instantanés génétiques des organismes vivants d'aujourd'hui, et non l'enregistrement complet du passé. Les scientifiques doivent inférer le chemin d'évolution le plus probable à partir des données dont ils disposent, en recherchant des modèles qui suggèrent comment les traits ont été transmis ou modifiés.
Une manière puissante d'y parvenir consiste à trouver le plus grand groupe de traits génétiques qui s'assemblent parfaitement sur un seul arbre sans contradiction. Imaginez un puzzle où la plupart des pièces s'emboîtent facilement, mais où quelques-unes sont déformées ou ont été façonnées par une évolution convergente — où des espèces non apparentées développent des traits similaires de manière indépendante. L'objectif est de trouver le plus grand ensemble de pièces formant une image cohérente, en ignorant celles qui brisent le modèle. C'est ce qu'on appelle le problème de la compatibilité maximale. Si trouver une seule bonne solution est difficile, trouver chaque solution optimale possible est encore plus difficile, et pourtant, c'est crucial pour construire un arbre généalogique complet et précis. Si les scientifiques ne trouvent qu'une seule solution, ils pourraient passer à côté d'histoires alternatives importantes que les données soutiennent.
Une équipe de chercheurs a développé une nouvelle approche pour résoudre ce puzzle difficile, combinant des techniques informatiques classiques avec des méthodes quantiques émergentes pour trouver non pas une, mais toutes les meilleures solutions d'arbres évolutifs. Leurs travaux se concentrent sur une étape spécifique du processus où l'ordinateur doit passer au crible des millions de possibilités pour trouver les plus grands groupes de traits compatibles. Les chercheurs ont découvert que, si les méthodes traditionnelles sont bonnes pour trouver une seule réponse, elles peinent souvent à capturer toute la diversité des solutions également valables. Pour y remédier, ils ont introduit une stratégie en deux parties : premièrement, ils ont créé un ensemble de règles pour réduire la taille massive du puzzle à une dimension gérable sans perdre aucune des réponses possibles ; deuxièmement, ils ont testé une nouvelle façon d'utiliser les ordinateurs quantiques pour échantillonner ces solutions, traitant la machine quantique non pas comme un solveur magique, mais comme un outil pour générer un ensemble diversifié de candidats qui peuvent être nettoyés et vérifiés par des ordinateurs classiques.
Les chercheurs ont commencé par examiner les données de centaines de milliers de séquences du virus SARS-CoV-2, un ensemble de données assez vaste pour tester les limites de la technologie actuelle. Ils ont découvert que la manière standard d'utiliser les ordinateurs quantiques pour résoudre ce problème n'était pas optimale. Typiquement, les algorithmes quantiques sont réglés pour appliquer strictement les règles, garantissant que chaque solution candidate suit parfaitement les lois du puzzle. Cependant, l'équipe a découvert que sur des dispositifs quantiques réels et bruités, cette rigueur était un obstacle. Au lieu de cela, ils ont découvert qu'il était préférable de laisser l'ordinateur quantique produire des candidats « désordonnés » qui pourraient enfreindre quelques règles, puis d'utiliser un programme informatique classique rapide pour les corriger. Ce processus de réparation est semblable à un éditeur qualifié prenant un brouillon et le polissant pour en faire une version finale parfaite. En laissant la machine quantique explorer un éventail plus large de possibilités, puis en nettoyant les résultats, ils ont pu trouver des solutions plus distinctes qu'en essayant de forcer la machine quantique à être parfaite dès le départ.
Pour rendre ce processus suffisamment efficace pour la technologie actuelle, l'équipe a également développé une méthode pour compresser le problème avant de l'envoyer à l'ordinateur quantique. Ils ont réalisé que de nombreuses parties des données génétiques étaient si prévisibles qu'elles pouvaient être retirées du calcul, à condition que les chercheurs gardent une trace de la manière de les réintégrer plus tard. Cela s'apparente à retirer le cadre d'un tableau pour voir la toile en dessous, tout en sachant exactement comment le réattacher plus tard. En appliquant ces règles de réduction sans perte, ils ont pu réduire un graphe complexe représentant les données génétiques, passant de centaines de nœuds à seulement une poignée. Dans un cas de test spécifique impliquant 350 échantillons de virus, leur méthode a réduit le problème d'un graphe de 64 points à un graphe minuscule et simple de seulement cinq points. Cela signifiait que l'étape finale de la recherche de la réponse devenait triviale, permettant de récupérer l'ensemble complet des arbres évolutifs optimaux avec certitude.
Les résultats de leurs expériences ont montré une différence claire entre trouver une réponse et trouver toutes les réponses. Lorsqu'ils utilisaient des outils classiques standards pour trouver la meilleure solution, ils réussissaient souvent à trouver un résultat unique de premier plan. Cependant, lorsqu'ils tentaient de trouver toutes les différentes manières dont les données pouvaient être organisées, ces mêmes outils passaient souvent à côté de nombreuses solutions valides, même après des milliers d'exécutions. Leur approche hybride, qui combinait la compression de graphe avec une méthode d'échantillonnage quantique modifiée, s'est avérée bien plus efficace pour découvrir cette diversité cachée. Sur un graphe de test de 64 points, leur méthode quantique modifiée a trouvé plus de solutions distinctes et vérifiées qu'une méthode de choix aléatoire lors de chaque essai. Bien que cela n'ait pas encore prouvé que les ordinateurs quantiques sont supérieurs aux classiques pour cette tâche, cela a démontré que la combinaison d'une réduction intelligente des données et de l'échantillonnage quantique est un moyen puissant de s'attaquer à des problèmes qui étaient auparavant trop vastes ou complexes pour être résolus complètement.
En fin de compte, ce travail suggère une nouvelle voie pour la biologie de l'évolution. En traitant le problème comme un système modulaire où les données sont d'abord simplifiées, puis échantillonnées, et enfin reconstruites, les scientifiques peuvent désormais manipuler des ensembles de données beaucoup plus importants qu'auparavant. Les chercheurs ont montré qu'ils pouvaient prendre un ensemble massif de séquences virales, en retirer les parties prévisibles, utiliser un dispositif quantique pour explorer le noyau complexe restant, puis reconstruire l'image complète avec une précision parfaite. Cette approche ne repose pas sur la perfection ou l'absence d'erreurs des ordinateurs quantiques ; elle les utilise plutôt comme une source d'idées diverses qui sont ensuite affinées par la logique classique. À mesure que la technologie quantique progresse, cette méthode combinant les forces de l'informatique classique et quantique pourrait permettre aux scientifiques de reconstruire l'histoire de la vie avec un niveau de détail et de complétude qui était auparavant hors de portée.
Noyé(e) sous les articles dans votre domaine ?
Recevez des digests quotidiens des articles les plus récents correspondant à vos mots-clés de recherche — avec des résumés techniques, dans votre langue.