Algoritmo Padrão de Alinhamento Global de Needleman-Wunsch

1.

Introdução

Nos últimos anos, a biologia tem se tornado cada vez mais uma ciência dependente de processamento de dados e o recente sequenciamento do genoma humano completo pelo
Projeto Genoma Humano – um esforço multinacional que recebeu extensa cobertura da mídia
– é um marco no desenvolvimento dessa nova biologia. Atualmente, inúmeras bases de dados espalhadas por todo o mundo armazenam quantidades impressionantes de dados biológicos, e elas estão crescendo exponencialmente em tamanho conforme os genomas de outras espécies são sequenciados.

i.

Sequências biomoleculares.

O genoma é o conjunto completo de moléculas de DNA dentro de qualquer célula de um organismo vivo que passou de uma geração para seus descendentes. O DNA (ácido desoxirribonucleico) é considerado o “projeto” da vida porque, como uma especificação, ele
“codifica” a informação necessária para produzir as proteínas requeridas para todos os processos celulares. De fato, é reconhecido como o que faz dois seres vivos serem biologicamente similares ou distintos.
O DNA é essencialmente uma cadeia dupla de moléculas mais simples chamadas nucleotídeos, amarrados juntos em uma estrutura helicoidal famosamente conhecida como a dupla hélice (figura 1). As duas cadeias, chamadas fitas, são complementares de modo que é possível deduzir uma fita através da outra. Os nucleotídeos são distinguidos por uma base nitrogenada que pode ser de quatro tipos: adenosina, citosina, guanina e timina. Essas bases são as moléculas que mantém a dupla hélice junta. Adenosina sempre se liga a timina ao passo que citosina sempre se liga a guanina, formando pares de bases. Pares de bases (pb) são a unidade mais comum de medição do tamanho do DNA. Felizmente, um DNA pode ser especificado unicamente pela listagem de sua sequência de nucleotídeos, ou pares de bases.
Portanto, para fins práticos, o DNA é abstraído como um longo texto sobre um alfabeto de quatro letras, cada um representando um