A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

Cada ser vivo carrega uma história escrita em seu DNA, um registro molecular de como as populações se moveram, misturaram-se e se separaram ao longo de milhares de anos. Para os cientistas, reconstruir essa história é como tentar montar um quebra-cabeça massivo e fragmentado, onde as peças são variações genéticas e a imagem é a árvore genealógica de uma espécie. Uma das formas mais confiáveis de rastrear a ancestralidade humana é observando o cromossomo Y, um pequeno pedaço de DNA passado quase inalterado de pai para filho. Como ele não se mistura com o DNA da mãe, o cromossomo Y atua como uma linha de descendência clara e ininterrupta, permitindo que os pesquisadores mapeiem os ramos profundos da árvore genealógica humana. No entanto, à medida que a quantidade de dados genéticos cresce, a tarefa de encontrar a estrutura correta da árvore torna-se incrivelmente difícil. O número de maneiras possíveis de organizar mesmo um número modesto de pessoas em uma árvore genealógica é tão vasto que excede a capacidade dos computadores padrão de verificar cada possibilidade uma por uma. Essa explosão combinatória forçou os cientistas a depender de atalhos, ou heurísticas, que tentam adivinhar a melhor resposta rapidamente, mas não garantem que ela seja a verdadeira.

Uma equipe de pesquisadores no CRS4, na Sardenha, desenvolveu um novo fluxo de trabalho computacional que aborda esse problema combinando duas estratégias distintas: dividir um problema gigante em partes menores e gerenciáveis e usar um tipo especializado de algoritmo de inspiração quântica para resolver essas partes. O trabalho deles foca nos dados do cromossomo Y humano, observando especificamente mudanças de uma única letra no código genético conhecidas como polimorfismos de nucleotídeo único. Os pesquisadores começaram com um conjunto de dados contendo informações genéticas de 150 amostras, as quais eles limparam para remover 72 amostras não informativas que careciam de variantes genéticas necessárias, deixando 78 populações masculinas para análise. Eles então usaram seu novo método para reconstruir a árvore evolutiva. Em vez de tentar resolver toda a árvore de uma vez, o que seria complexo demais para a tecnologia atual, eles dividiram a tarefa em duas decisões principais. Primeiro, determinaram quais grupos de pessoas deveriam ser agrupados juntos na árvore. Segundo, descobriram onde o início da árvore, a raiz, deveria ser colocado para mostrar a direção do tempo.

Para tomar essas decisões, os pesquisadores traduziram o problema biológico em um formato matemático conhecido como problema de otimização binária quadrática não restrita. Em termos simples, esta é uma forma de transformar a busca pela melhor árvore na busca pelo ponto mais baixo em uma paisagem complexa de colinas e vales, onde o ponto mais baixo representa a história familiar mais provável. O desafio é que essa paisagem é grande demais para ser explorada de uma só vez. A solução da equipe foi usar uma técnica chamada decomposição ADMM, que divide a paisagem massiva em seções menores e sobrepostas. Cada seção é resolvida independentemente e, em seguida, os resultados são costurados para formar um todo consistente. Isso permite que o sistema lide com um tamanho de problema que, de outra forma, seria impossível para um único computador processar.

Para resolver essas seções menores, a equipe empregou um método chamado otimização quântica contra-diabética digitalizada. Essa abordagem utiliza os princípios da mecânica quântica para encontrar o ponto mais baixo na paisagem de forma muito rápida. Ao contrário de outros métodos quânticos que exigem um processo lento e iterativo de tentativa e erro, essa técnica calcula o caminho para a solução em uma única passagem direta. Os pesquisadores testaram seu fluxo de trabalho em uma simulação de computador livre de ruídos que imita o comportamento de um processador quântico. Eles descobriram que o método reconstruiu com sucesso a árvore genealógica das 78 populações. A árvore resultante posicionou a raiz profundamente dentro de linhagens africanas, um achado que se alinha com o entendimento científico estabelecido sobre as origens humanas. Além disso, embora cada agrupamento identificado pelo novo método fosse consistente com uma técnica de construção de árvores padrão e amplamente aceita chamada Neighbor-Joining, o novo método recuperou apenas 40% dos agrupamentos encontrados na árvore de referência Neighbor-Joining, indicando que, embora sua abordagem seja precisa, ela identificou menos clusters totais do que o método padrão.

O estudo demonstra que essa abordagem híbrida, que combina a divisão de grandes problemas com resolvedores eficientes de estilo quântico, é um caminho viável para a genômica de populações. Ela oferece uma maneira de ir além do palpite dos atalhos tradicionais sem exigir o hardware massivo e propenso a erros que os computadores quânticos de escala total atualmente precisam. Ao provar que podem resolver esses problemas difíceis de reconstrução de árvores em um dispositivo quântico simulado, os pesquisadores mostraram que a tecnologia está pronta para ser aplicada a conjuntos de dados ainda maiores no futuro. O trabalho deles fornece um pipeline claro, passo a passo, que pega dados genéticos brutos e os transforma em uma árvore genealógica enraizada e anotada, completa com os marcadores genéticos específicos que definem cada ramo. Esse feito sugere que o campo está se movendo em direção a um futuro onde a complexidade total da história evolutiva humana pode ser mapeada com maior precisão e menor dependência de aproximação.