A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

Cada ser vivo porta una historia escrita en su ADN, un registro molecular de cómo las poblaciones se han desplazado, mezclado y separado a lo largo de miles de años. Para los científicos, reconstruir esta historia es como intentar ensamblar un rompecabezas masivo y fragmentado donde las piezas son variaciones genéticas y la imagen es el árbol genealógico de una especie. Una de las formas más fiables de rastrear la ascendencia humana es observando el cromosoma Y, una pequeña pieza de ADN que se transmite casi sin cambios de padre a hijo. Debido a que no se mezcla con el ADN de la madre, el cromosoma Y actúa como una línea de descendencia clara e ininterrumpida, lo que permite a los investigadores mapear las ramas profundas del árbol genealógico humano. Sin embargo, a medida que crece la cantidad de datos genéticos, la tarea de encontrar la estructura de árbol correcta se vuelve increíblemente difícil. El número de formas posibles de organizar incluso un número modesto de personas en un árbol genealógico es tan vasto que supera la capacidad de las computadoras estándar para comprobar cada posibilidad una por una. Esta explosión combinatoria ha obligado a los científicos a confiar en atajos, o heurísticas, que adivinan la mejor respuesta rápidamente pero no garantizan que sea la verdadera.

Un equipo de investigadores en CRS4 en Cerdeña ha desarrollado un nuevo flujo de trabajo computacional que aborda este problema combinando dos estrategias distintas: dividir un problema gigante en piezas más pequeñas y manejables, y utilizar un tipo especializado de algoritmo de inspiración cuántica para resolver esas piezas. Su trabajo se centra en los datos del cromosoma Y humano, centrándose específicamente en los cambios de una sola letra en el código genético conocidos como polimorfismos de nucleótido único. Los investigadores comenzaron con un conjunto de datos que contenía información genética de 150 muestras, las cuales limpiaron para eliminar 72 muestras no informativas que carecían de las variantes genéticas necesarias, dejando 78 poblaciones masculinas para el análisis. Luego utilizaron su nuevo método para reconstruir el árbol evolutivo. En lugar de intentar resolver todo el árbol a la vez, lo cual sería demasiado complejo para la tecnología actual, dividieron la tarea en dos decisiones principales. Primero, determinaron qué grupos de personas deberían agruparse juntos en el árbol. Segundo, determinaron dónde debería colocarse el mismísimo principio del árbol, la raíz, para mostrar la dirección del tiempo.

Para tomar estas decisiones, los investigadores tradujeron el problema biológico a un formato matemático conocido como optimización binaria cuadrática no restringida. En términos sencillos, esta es una forma de convertir la búsqueda del mejor árbol en un juego de encontrar el punto más bajo en un paisaje complejo de colinas y valles, donde el punto más bajo representa la historia familiar más probable. El desafío es que este paisaje es demasiado grande para explorarlo todo a la vez. La solución del equipo fue utilizar una técnica llamada descomposición ADMM, que divide el paisaje masivo en secciones más pequeñas y superpuestas. Cada sección se resuelve de forma independiente y luego los resultados se vuelven a unir para formar un todo coherente. Esto permite al sistema manejar un tamaño de problema que, de otro modo, sería imposible de procesar para una sola computadora.

Para resolver estas secciones más pequeñas, el equipo empleó un método llamado optimización cuántica contra-diabética digitalizada. Este enfoque utiliza los principios de la mecánica cuántica para encontrar el punto más bajo en el paisaje de manera muy rápida. A diferencia de otros métodos cuánticos que requieren un proceso lento e iterativo de ensayo y error, esta técnica calcula la ruta hacia la solución en un solo paso directo. Los investigadores probaron su flujo de trabajo en una simulación computacional libre de ruido que imita el comportamiento de un procesador cuántico. Descubrieron que el método reconstruyó con éxito el árbol genealógico de las 78 poblaciones. El árbol resultante situó la raíz profundamente dentro de los linajes africanos, un hallazgo que concuerda con el conocimiento científico establecido sobre los orígenes humanos. Además, aunque cada agrupación identificada por su nuevo método era consistente con una técnica de construcción de árboles ampliamente aceptada llamada Neighbor-Joining, el nuevo método solo recuperó el 40% de las agrupaciones encontradas en el árbol de referencia de Neighbor-Joining, lo que indica que, si bien su enfoque es preciso, identificó menos grupos totales que el método estándar.

El estudio demuestra que este enfoque híbrido, que combina la división de problemas grandes con resolvedores eficientes de estilo cuántico, es un camino viable hacia adelante para la genómica de poblaciones. Ofrece una forma de ir más allá de las conjeturas de los atajos tradicionales sin requerir el hardware masivo y propenso a errores que las computadoras cuánticas de escala completa necesitan actualmente. Al demostrar que pueden resolver estos difíciles problemas de reconstrucción de árboles en un dispositivo cuántico simulado, los investigadores han demostrado que la tecnología está lista para aplicarse a conjuntos de datos aún más grandes en el futuro. Su trabajo proporciona un flujo de trabajo claro y paso a paso que toma los datos genéticos brutos y los convierte en un árbol genealógico enraizado y anotado, completo con los marcadores genéticos específicos que definen cada rama. Este logro sugiere que el campo se mueve hacia un futuro donde la complejidad total de la historia evolutiva humana puede mapearse con mayor precisión y con menor dependencia de la aproximación.