Programação Dinâmica e Bioinformática: Construindo um Algoritmo de Alinhamento Genético em C e como chegaram ao BLAST

Problema

A comparação entre sequências biológicas é um dos principais desafios para entendimento da bioinformática . Identificar similaridade entre sequências de DNA permite inferir relações evolutivas, possíveis homologias e regiões conservadas entre organismos distintos.

Entretanto, a análise manual de sequências genéticas torna-se inviável devido ao volume de dados biológicos existentes. Além disso, determinar se duas sequências possuem evidências de homologia exige não apenas comparação direta de nucleotídeos, mas também métricas quantitativas de alinhamento, identidade e conservação estrutural.

Dessa forma, surge a necessidade de algoritmos capazes de alinhar sequências biologicamente, calcular métricas de similaridade, identificar regiões conservadas e auxiliar na inferência computacional de homologia.

Objetivo

Desenvolver um algoritmo em linguagem C baseado no método de alinhamento global de Needleman-Wunsch utilizando programação dinâmica e backtracking, capaz de alinhar sequências de DNA, reconstruir o alinhamento ótimo, calcular métricas biológicas de similaridade, identificar regiões conservadas, estimar cobertura entre sequências e inferir níveis de evidência de homologia biológica.

O sistema também busca demonstrar como técnicas clássicas de programação dinâmica podem ser aplicadas em problemas reais da bioinformática computacional.

Introdução

A comparação de sequências biológicas é uma das operações fundamentais da bioinformática moderna. Por meio dela, é possível identificar padrões conservados, estimar similaridade genética e analisar possíveis relações evolutivas entre organismos distintos (CUNHA, 2019).

Entre os métodos clássicos utilizados para esse tipo de problema está o algoritmo de Needleman-Wunsch algorithm, proposto por Saul Needleman e Christian Wunsch em 1970. O método utiliza programação dinâmica para encontrar o alinhamento global ótimo entre duas sequências biológicas, construindo uma matriz de pontuação baseada em matches, mismatches e gaps (NEEDLEMAN; WUNSCH, 1970).

A lógica matemática do algoritmo segue a seguinte recorrência:

Após o preenchimento da matriz, o algoritmo utiliza backtracking para reconstruir o caminho ótimo do alinhamento a partir das decisões armazenadas durante o processamento.

Segundo Cunha (2019), métodos exatos baseados em alinhamento produzem resultados biologicamente mais precisos, porém possuem alto custo computacional quando aplicados em grandes sequências genômicas. Esse fator motivou o surgimento de ferramentas heurísticas modernas, como o BLAST, capazes de reduzir significativamente o tempo de execução em bancos biológicos extensos.

Neste projeto, foi desenvolvida uma implementação em linguagem C baseada no algoritmo de Needleman-Wunsch utilizando programação dinâmica e backtracking. Além do alinhamento global, o sistema também realiza cálculos de identidade biológica, cobertura entre sequências, quantidade de gaps, mismatches, matches e identificação de blocos conservados, permitindo gerar inferências heurísticas sobre similaridade biológica e possíveis evidências de homologia.

Referência

ALTSCHUL, Stephen F. et al. Basic local alignment search tool. Journal of Molecular Biology, Londres, v. 215, n. 3, p. 403–410, 1990.

MOUNT, David W. Bioinformatics: sequence and genome analysis. 2. ed. New York: Cold Spring Harbor Laboratory Press, 2004.

CUNHA, Rafael Neiva da. Avaliação de estratégias alignment-free para determinar o fator de pruning em comparação paralela de sequências. 2019. Trabalho de Conclusão de Curso (Bacharelado em Engenharia da Computação) — Universidade de Brasília, Brasília, 2019. Disponível em: TCC Rafael Neiva da Cunha — UnB. Acesso em: 18 maio 2026.

NEEDLEMAN, Saul B.; WUNSCH, Christian D. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, Londres, v. 48, n. 3, p. 443–453, 1970.

NATIONAL CENTER FOR BIOTECHNOLOGY INFORMATION. Pisang Klutuk DNA sequence. Disponível em: NCBI — Pisang Klutuk. Acesso em: 18 maio 2026.

NATIONAL CENTER FOR BIOTECHNOLOGY INFORMATION. Musa acuminata DNA sequence. Disponível em: NCBI — Musa acuminata. Acesso em: 18 maio 2026.

OREGON STATE UNIVERSITY. Applied Bioinformatics — Chapter 3. Disponível em: Applied Bioinformatics Chapter 3. Acesso em: 18 maio 2026.