Sequence-to-graph alignment based copy number calling using a network flow formulation

O artigo apresenta o Floco, um método inovador que utiliza uma formulação de fluxo em rede para melhorar a precisão da chamada de número de cópias (CN) em grafos genômicos, superando as limitações das abordagens tradicionais baseadas em referência linear e demonstrando ganhos de até 43% na acurácia das previsões.

O essencial

Imagine que o nosso genoma (o nosso "manual de instruções" biológico) é como uma receita de bolo. Às vezes, para fazer um bolo perfeito, você precisa de duas xícaras de farinha, em vez de uma. Outras vezes, você precisa de três. Isso é o que chamamos de "Variação do Número de Cópias" (CN). Se você errar a quantidade de farinha, o bolo pode não crescer ou ficar estragado. Da mesma forma, erros no número de cópias do nosso DNA podem causar doenças.

O problema é que, até agora, os cientistas tentavam ler essa receita comparando-a com um único modelo de receita padrão (o genoma de referência linear). O problema é que esse modelo padrão não tem todas as variações possíveis. É como tentar encaixar uma peça de um quebra-cabeça complexo em um buraco redondo: não funciona bem, e você perde informações importantes.

Aqui entra o Floco, a nova ferramenta apresentada neste artigo.

O Problema: O Mapa vs. O Terreno

Antes, os cientistas olhavam para cada pedaço do DNA isoladamente, contando quantas vezes ele aparecia nas leituras (como contar quantas pessoas estão em uma sala). Mas, se houver ruído, erros de leitura ou se o DNA estiver muito parecido com outras partes, essa contagem simples falha. É como tentar adivinhar quantas pessoas estão em um estádio olhando apenas para uma única câmera, sem saber se as pessoas estão se movendo ou se a câmera está tremendo.

Além disso, quando usamos um "mapa" em forma de grafo (uma rede complexa de caminhos possíveis, em vez de uma linha reta), surgem novos problemas: se você contar cada "nó" (ponto do mapa) separadamente, pode acabar com uma história que não faz sentido. Por exemplo, o mapa pode dizer que você tem 2 cópias de um gene no início do caminho e 0 no final, o que é biologicamente impossível se o caminho for contínuo.

A Solução: O Floco e o "Fluxo de Trânsito"

O Floco (que significa "Fluxo" em latim, brincadeira com o nome) resolve isso usando uma ideia inteligente: o fluxo de rede.

Imagine que o genoma é uma estrada de mão dupla e as leituras de DNA são carros viajando por ela.

1. O Contador Individual (Antes do Floco): Você para em cada posto de pedágio e conta quantos carros passaram. Às vezes, o contador erra, ou o carro pula o pedágio. Você fica com números confusos: "Aqui passaram 5 carros, ali passaram 0, mas a estrada continua".
2. O Sistema de Trânsito (O Floco): O Floco não olha apenas para um pedágio. Ele olha para a estrada inteira. Ele sabe que, se 10 carros entraram na estrada, 10 carros devem sair (ou estacionar em algum lugar). Ele usa matemática avançada (Programação Linear Inteira) para garantir que o "fluxo" de carros seja consistente do início ao fim.

Se o contador individual diz que há 0 carros em um trecho, mas a estrada anterior e posterior estão cheias, o Floco entende: "Ei, esse contador deve ter errado! Vamos ajustar para que o fluxo faça sentido".

Como eles testaram?

Os autores do Floco pegaram dados reais de sequenciamento de DNA (como fotos de carros em alta velocidade) de humanos e até de batatas (sim, batatas têm genomas complexos!) e compararam três coisas:

1. Leituras de alta precisão (HiFi).
2. Leituras de longo alcance, mas com mais erros (ONT).
3. Montagens lineares de DNA.

O Resultado:
O Floco conseguiu alinhar essas três fontes de informação com uma precisão impressionante (até 93% de concordância). Mais importante: ao usar a lógica do "fluxo de trânsito", a precisão das previsões aumentou em até 43% comparado aos métodos antigos que apenas contavam leituras isoladamente.

Por que isso é importante?

1. Diagnóstico de Doenças: Ajuda a encontrar erros no DNA que causam doenças, que antes passavam despercebidos porque o "mapa padrão" não os tinha.
2. Controle de Qualidade: Funciona como um detector de mentiras para os próprios mapas genéticos. Se o Floco diz que uma parte do mapa tem 0 cópias (está vazia), mas deveria ter, ele avisa: "Cuidado, essa parte do mapa pode estar errada ou quebrada".
3. Futuro: Com o avanço da medicina personalizada, onde cada pessoa tem seu próprio "mapa" genético, ferramentas como o Floco serão essenciais para entender como nossas variações únicas afetam nossa saúde.

Em resumo: O Floco é como um gerente de trânsito inteligente que olha para o mapa completo do genoma e corrige contagens erradas, garantindo que a história do nosso DNA faça sentido do início ao fim, permitindo que os cientistas vejam variações que antes eram invisíveis.

Resumo técnico

1. O Problema

A variação do número de cópias (CN - Copy Number) de sequências genéticas entre indivíduos está frequentemente associada a diferenças fenotípicas e doenças. Tradicionalmente, a chamada de CN é realizada mapeando leituras de sequenciamento (reads) para um genoma de referência linear e estimando o CN com base na profundidade de leitura (read depth).

No entanto, essa abordagem enfrenta limitações significativas:

• Viés de Referência: Sequências e rearranjos genômicos ausentes no genoma linear de referência não são mapeados corretamente, levando a erros de estimativa.
• Inconsistência em Grafos: Com o advento de pangenomas representados como grafos (que incluem mais diversidade e variantes ausentes no linear), a estimativa de CN pode ser feita por nó do gráfico. Contudo, estimar o CN de cada nó individualmente ignora a topologia do gráfico. Isso pode levar a resultados inconsistentes (ex: um nó com CN=1 conectado a um nó com CN=0 em um caminho contínuo), especialmente devido a erros de sequenciamento, mau alinhamento ou erros de montagem que afetam a cobertura local.

2. Metodologia: O Método Floco

Os autores propõem o Floco, uma ferramenta para chamada de CN em genomas grafos utilizando uma formulação de fluxo de rede resolvida via Programação Linear Inteira (ILP).

O fluxo de trabalho do Floco é dividido nas seguintes etapas:

1. Entrada: Recebe um gráfico de genoma (formato GFA) e alinhamentos de leituras contra esse gráfico (formato GAF).
2. Cálculo de Probabilidades de CN:
   • Calcula a cobertura de pares de bases para cada nó.
   • Modela a distribuição de cobertura usando uma distribuição Binomial Negativa (NB) para nós com CN > 0 e uma distribuição exponencial discretizada para CN = 0 (para modelar erros de alinhamento).
   • Gera probabilidades de CN para cada nó individualmente com base na cobertura observada.
3. Formulação de Fluxo de Rede:
   • Transforma o problema em um problema de fluxo de custo mínimo (adaptado para maximizar probabilidade) em um gráfico bidirecionado.
   • Nós e Arestas: Cada nó do gráfico de genoma é representado com extremidades esquerda e direita. Arestas conectam essas extremidades, incluindo arestas de "superfonte" ($s$) e "supersumidouro" ($t$).
   • Restrições:
     • O fluxo que entra em uma extremidade de um nó deve ser igual ao fluxo que sai da extremidade oposta (conservação de fluxo).
     • A soma do fluxo através de um nó define o seu CN inteiro ($x_v$).
   • Função Objetivo: Maximizar a soma das probabilidades logarítmicas dos CNs atribuídos aos nós, penalizada por custos nas arestas (ex: penalidade "cara" para arestas não suportadas por muitas leituras ou arestas de superfonte/sumidouro).
4. Resolução: O problema é resolvido usando o solucionador Gurobi ILP, garantindo que a atribuição final de CN seja consistente com a topologia do gráfico (ou seja, os CNs formam "caminhadas" válidas através do gráfico).

3. Contribuições Chave

• Consistência Topológica: O principal avanço é garantir que as chamadas de CN sejam consistentes com a estrutura do gráfico, corrigindo erros locais de cobertura que levariam a atribuições impossíveis biologicamente.
• Abordagem Geral para Grafos: Preenche uma lacuna na ferramenta de bioinformática, sendo o primeiro método focado especificamente em chamada de CN para grafos de pangenoma usando fluxo de rede.
• Robustez a Ruído: O método é capaz de distinguir entre ausência real de sequência (deleção) e falhas de alinhamento ou ruído de sequenciamento, agregando sinais de nós vizinhos.

4. Resultados

Os autores avaliaram o Floco em 15 conjuntos de dados, utilizando três gráficos diferentes (dois de montagem e um pangenoma HPRC) e três fontes de dados (HiFi, ONT e montagens lineares "trituradas" em leituras).

• Aumento de Precisão: A adição da formulação de fluxo de rede aumentou a precisão das previsões de CN em até 43% em comparação com a estimativa baseada apenas na profundidade de leitura (sem fluxo).
  • No caso de validação com o genoma CHM13 (in-sample), a precisão atingiu 99,7% para nós após o fluxo, com erro < $4 \times 10^{-5}$.
  • Em coberturas baixas (1x), a melhoria foi drástica: a taxa de erro foi reduzida em aproximadamente 15 vezes para dados ONT e HiFi.
• Concordância entre Tecnologias: O método demonstrou alta robustez. A concordância entre as previsões feitas a partir de HiFi, ONT e montagens lineares atingiu 93,2% da sequência total no gráfico de montagem humana (HG01114).
• Controle de Qualidade (QC) de Montagem: O Floco foi capaz de identificar nós com CN=0 em montagens de onde as leituras deveriam estar presentes, sinalizando potenciais erros de montagem (misassemblies) ou regiões de baixa complexidade.
• Desempenho Computacional:
  • O método é leve: em gráficos de montagem, o tempo de execução varia de 8 a 22 minutos (1 thread) e o uso de memória não excede 3,1 GB.
  • Em gráficos de pangenoma mais complexos, o tempo varia de 40 min a 3 horas, com uso de memória de até 53 GB.
  • O tempo de chamada de CN é uma fração do tempo necessário para alinhar as leituras ao gráfico.

5. Significado e Impacto

O trabalho do Floco é fundamental para a era dos pangenomas. À medida que a genômica se afasta de referências lineares únicas para grafos de pangenoma, ferramentas que conseguem interpretar a topologia complexa desses grafos são essenciais.

• Validação de Montagem: Oferece uma maneira robusta de validar a qualidade de montagens de genoma, identificando erros estruturais.
• Genotipagem de Variações Estruturais: Permite a genotipagem precisa de duplicações segmentares e outras variações de número de cópias que são difíceis de detectar em referências lineares.
• Associação Fenotípica: Ao fornecer estimativas de CN mais precisas e consistentes, o Floco facilita estudos de associação entre variações de CN e fenótipos ou doenças, superando o viés de referência que limitava abordagens anteriores.

Em resumo, o Floco representa um avanço técnico significativo ao integrar modelos estatísticos de cobertura com otimização de fluxo de rede, transformando a chamada de CN em grafos de uma tarefa propensa a erros locais em um processo globalmente consistente e altamente preciso.