Alinhamento de sequências biológicas na Bioinformática

Alinhamento de sequências biológicas na Bioinformática Diego I. Macedo Centro Universitário Anhanguera de Niterói – UNIAN Niterói – RJ 2014 Aprovado por: Deise Galvão, André Farias, João Fernando

Resumo. A Bioinformática é uma linha de pesquisa relativamente nova, tendo início na década de 90, que envolve diversas linhas de conhecimento – Ciências da computação, matemática, estatística e biologia molecular. Esta linha de pesquisa tem como principal tarefa desvendar a enorme quantidade de dados que vem sendo obtida através dos sequenciamentos de DNA e RNA. Através de alinhamentos dessas sequências, comparações se tornam possíveis e nos tem levado a grandes avanços nos estudos de biologia molecular. Entretanto, esses alinhamentos e comparações de sequencias são problemas de grande dificuldade. Procuramos no presente trabalho, concatenar estudos e técnicas mais conhecidas sobre alinhamentos de sequências, começando pela introdução de conceitos, embasamento matemático, expondo algoritmos básicos para busca de alinhamentos ótimos e apresentando comparativos e análises desses algoritmos.

1.

Introdução A Biologia Molecular é o estudo da Biologia em nível molecular, com especial foco no estudo da estrutura e função do material genético e seus produtos de expressão, as proteínas. Mais concretamente, a Biologia Molecular investiga as interações entre os diversos sistemas celulares, incluindo a relação entre DNA, RNA e síntese proteica. É um campo de estudo alargado, que abrange outras áreas da Química, em especial Genética e Bioquímica. [W. T. ASTBURY, 1961]. Por volta dos anos 1950, experimentos apontaram o DNA como parte de cromossomos que continha genes. Um foco em novos modelos de organismos, tais como vírus e bactérias, juntamente com a descoberta da dupla hélice do DNA, em 1953, marcaram a transição para a era da biologia molecular. Nos anos seguintes, químicos desenvolveram técnicas para sequenciamento de proteínas[W. T. ASTBURY, 1961]. Em biologia molecular, sequenciamento é o nome dado ao processo de determinação da ordem sequencial das partes constituintes de um biopolímero não ramificado, isto é, a ordem de nucleotídeos de uma molécula de DNA ou RNA, ou de aminoácidos de uma proteína. O sequenciamento resulta numa representação linear simbólica conhecida como sequência, a qual sucintamente resume a estrutura da molécula sequenciada. [Keith Roberts, et al., 2007].

1

A Bioinformática é uma área interdisciplinar que combina Ciências da computação, matemática, estatística e biologia molecular, tendo surgido na década de 90, quando produção de dados biológicos atingiram níveis tão altos que tornaram as análises manuais de sequências de DNA uma alternativa absurda para o estudo de genomas. Um dos problemas mais desafiadores no campo da Bioinformática é o alinhamento de sequências biológicas. O alinhamento de sequências de DNA, RNA ou aminoácidos é essencial no estudo de suas similaridades. Por muitas vezes, as semelhanças encontradas levam a funções análogas, fornecendo valiosas informações evolutivas que permitem inferir a história evolutiva dessas sequências, entretanto, três ou mais sequências de comprimento biologicamente relevantes, podem ser computacionalmente muito complicados e são classificados como um NPCompleto [L. Wang & T. Jiang,1994]. O problema básico com algoritmos de sequenciamento é a sua complexidade exponencial devido ao consideravelmente grande conjunto de dados de entrada. Esses algoritmos de alinhamento de sequências buscam executar suas funções de forma a encontrar o maior grau de similaridade entre as sequências comparadas. Ou seja, a ideia central é minimizar a diferença, de modo a atingir um estado chamado “alinhamento ótimo”. Para o entendimento de como se processa um alinhamento entre duas ou mais sequencias e os seus respectivos graus de similaridade, concatenaremos conceitos conhecidos sobre o tema e alguns algoritmos mais conhecidos que foram desenvolvidos para a solução desse problema serão citados.

2.

Alinhamento de Sequências biológicas Neste capítulo é feito uma pequena introdução teórica sobre sequências biológicas e alinhamento de sequências.

2.1.

Sequências Biológicas Uma sequência biológica pode ser composta de DNA, RNA ou proteínas. O DNA ou ADN (ácido desoxirribonucleico) é um composto orgânico, em uma estrutura de dupla hélice [F.H.C. Crick & J.D. Watson, 1953], que contém informações sobre a estrutura, informações genéticas e funcionamento de um organismo. O DNA é formado por nucleotídeos que por sua vez consistem em três partes: fosfato, pentose (açucar) e uma base nitrogenada [A. Silverstein, et al, 2008]. As bases nitrogenadas encontradas no DNA são: adenina (A), citosina (C), guanina (G) e timina (T). EM um DNA cada base nitrogenada de uma fita é ligada a outra base corresponde na outra fita, formando um par de base. Esses pares de base são Adenina com Timina e Citosina com Guanina, conforme ilustrado na Figura 1.

2

Figura 1. DNA e RNA: diferenças estruturais e suas bases nitrogenadas. Fonte: [M.S. Nicholas, 2011]

O RNA ou ARN (ácido ribonucleico) também é um composto orgânico formado por nucleotídeos, porém possui uma estrutura de hélice simples. Além disso, no lugar da base nitrogenada timina, encontramos no RNA a base nitrogenada uracila (U), formando o par com Uracila. Uma proteína é codificada por uma sequência de três bases nitrogenadas, por meio de uma estrutura de RNA chamada RNA mensageiro (RNAm). Assim, com os 4 pares de bases são gerados 64 tipos de códons, porém apenas 20 proteínas são codificadas por eles.

2.2.

Representações e conceitos As moléculas consideradas nesse tipo de estudo, são moléculas de DNA, RNA e de proteínas. Tais moléculas tratam-se de polímeros que podem ser representadas por uma sequência de caracteres. A alinhamento é uma comparação de duas ou mais dessas sequências de caracteres que visa identificar similaridades entre sequências, de maneira a inferir características nas mesmas. O processo consiste em se organizar as sequências em linhas e colunas, de forma que cada linha represente uma sequência e que suas regiões associadas estejam no mesmo conjunto de colunas. Todas as linhas deverão ter o mesmo comprimento, e isto será possível mediante da eventual inserção de lacunas nas sequências. O alinhamento de duas sequências é chamado de dois-a-dois e o alinhamento de um número maior de sequências sendo chamado de alinhamento múltiplo. Para representarmos um alfabeto, utilizamos o símbolo ∑ como um conjunto finito, não vazio, de caracteres ou símbolos, no qual o símbolo ‘-‘ representará uma lacuna.

3

Exemplo do alfabeto das bases nitrogenadas: ∑ = { A, C, G, T, −}, sendo “A”, “C”, “G”, “T” e “-“, respectivamente as bases nitrogenadas Adenina, Citosina, Guanina, Timina e o ““ sendo uma representação de lacuna(Ou GAP). Então, seja uma sequência S sobre ∑ uma cadeia de caracteres: 𝑆 = (𝑐1 , 𝑐2 , ⋯ , 𝑐𝑛 ) ∈ ∑ 𝑛 , ∀𝑛 ∈ 𝑍+ . Sendo neste caso, o comprimento, ou tamanho da cadeia é n = | S |, onde | S | é o tamanho total de S. Um segmento S[i..j], também como podemos chamar, fragmento, é uma sequência definida para i menor que j, correspondendo a um trecho de S, contíguo ou não, ou seja: S[i..j] = (𝑐1 , 𝑐𝑖+1 , ⋯ , 𝑐𝑗 ).

Figura 2. Uma Sequência possível de S

Figura 3. Sequência definida de S.

2.3.

Alinhamento Simples Podemos descrever a relação entre duas sequências que chamaremos de 𝑆1 e 𝑆2 realizando um alinhamento simples. Este processo, como dito anteriormente, consiste em introduzir lacunas, representadas pelo símbolo ‘-‘, nos segmentos. Isso é feito de modo que os caracteres nas mesmas colunas sejam, em sua maioria, idênticos. Chamamo-los de Match. Essas lacunas podem ser inseridas tanto nas extremidades, quanto no interior das sequências, de modo que, 𝑆1 [𝑗] 𝑒 𝑆2 [𝑗], em uma determinada posição ‘j’, não sejam simultaneamente lacunas. Nomeamos essa propriedade de alinhamento livre de colunas em branco.

C T G C A A T C - G C A - T Figura 4. Um alinhamento possível para 𝑆1 = CTGCAAT e 𝑆2 = CGCAT.

Existem diversas possibilidades de alinhamento para as sequências. Para isso, existem técnicas que avaliam o “grau de similaridade” entre elas. Essas táticas permitem decidir, dentre as possibilidades, qual seria a de alinhamento ótimo. Avaliamos o grau de complexidade desse problema, computando quantos alinhamentos (ƞ) possíveis existem entre as sequências dadas, da seguinte maneira: 

4

Se: |𝑆1 | = |𝑆2 | , sem espaços incluídos, existe apenas uma alinhamento possível, ou seja: ƞ = 1.



Se: n = max { |𝑆1 |, |𝑆2 | }, com espaços incluídos, no pior caso teremos o cálculo apresentado na Figura 7.

Figura 5. Cálculo de pior caso. Fonte: [Brito, 2003]

Para o cálculo de “grau de similaridade”, deve-se obter uma padronização, e para isso, Se |𝑆1 | = 𝑛1 e |𝑆2 | = 𝑛2 , sendo 𝑛1 ≠ 𝑛2 , insere-se lacunas para que as duas cadeias finais tenham o mesmo tamanho, ou seja: |𝑆′1 | = |𝑆′2 | = 𝑛.

2.4.

Alinhamento Múltiplo Alinhamento múltiplo de sequências consiste em um alinhamento de três ou mais sequências biológicas, que pode ser representado como A, correspondendo a uma matriz 𝐴𝑖𝑗 de ordem k x n, onde k seja um número inteiro positivo com entradas em ∑ onde max { n ≥ 𝑛𝑖 , ∀= 1. . 𝑘 } de modo que a linha 𝐴𝑖 do alinhamento seja a sequência 𝑆𝑖 com possíveis lacunas entre seus caracteres. Se k igual a 2, o problema pode ser chamado de Alinhamento simples ou alinhamento de pares de sequências, enquanto se k maior que 2, podemos chamar de Alinhamento múltiplo ou Alinhamento de várias sequencias.

2.5.

Métodos de alinhamentos de sequências Existem alguns tipos de métodos para realizar os alinhamentos de sequências, cada um com sua motivação, se sobressaem dentro de um contexto que serão analisados a seguir.

2.5.1. Matriz de pontos

5

A análise por matriz de pontos é uma forma simples de comparação entre duas sequências, que visa buscar possíveis alinhamentos entre elas [J. Xiong, 2006]. Além disso, o método também é utilizado para encontrar repetições diretas e invertidas de sequência de proteínas e DNA, e predizer regiões no RNA que são complementares.

2.5.2. Alinhamento Local O alinhamento Local tem como propósito encontrar e extrair as sequências comparadas um ou mais segmentos que contenham alta similaridade, onde nesse caso, a avaliação é feita de forma parcial, ou seja, apenas os segmentos selecionados serão avaliados. Geralmente este tipo de alinhamento é utilizado na montagem de genomas e na busca de segmentos homólogos em banco de dados públicos. Duas ferramentas de busca de alinhamento local muito conhecidas são o FAST - Fast Alignment [PEARSON & LIPMAN, 1988] e BLAST – Basic Local Alignment Search Tool [ALTSCHUL et al., 1997].

2.5.3. Alinhamento Global O alinhamento Global é o tipo mais comum de alinhamento, este envolve uma comparação de uma extremidade a outra e após a inclusão das lacunas, as sequências são alinhadas uma sobre a outra de forma que seja aplicada uma avaliação do seu grau de similaridade. Geralmente esse tipo de alinhamento é utilizado para determinar regiões conservadas entre sequências homólogas. Duas ferramentas conhecidas que realizam esse tipo de alinhamento são o CLUSTAL [CLUSTAL, 2010] e MULTALIN [MULTALIN, 2010].

2.5.4. Avaliação de grau de similaridade Uma das formas de avaliação é atribuir pontuação no alinhamento de duas sequências com a estratégia de associar a cada coluna j dessas sequências uma pontuação 𝑤𝑗 . As pontuações atribuídas podem ser vistas na tabela da Figura 8.

𝑆1 [𝑗] = 𝑆2 [𝑗] 𝑆1 [𝑗] ≠ 𝑆2 [𝑗] ≠ ‘-‘ 𝑆1 [𝑗] = ‘-‘

Match Mismatch Mismatch

+1 -1 -2

Figura 6. Tabela de pontuação. Fonte: [Brito, 2003]

Usamos a seguinte função objetivo, como é mostrado na Figura 9, onde maiores valores f indicam que 𝑆1 e 𝑆2 são similares.

6

Figura 7. Função objetivo de grau de similaridade. Fonte: [Brito, 2003]

Como exemplo, podemos considerar dois alinhamentos possíveis das sequências para 𝑆1 = CTGCAAT e S2 = TCGCATA 𝑆1 C T G C A A T 𝑆2 T C G C A T A Figura 8. Exemplo de sequências.

Conforme pode ser observado no exemplo da Figura 11, o alinhamento 1 é maior que o alinhamento 2. Esse critério pode ser utilizado para comparar diversas sequências a fim de descobrir quais são as mais semelhantes entre si. Alinhamento 1 𝑆1 - C T G C A A T 𝑆2 T C - G C A - T A -2 1 -2 1 1 1 -2 1 -2 ( 1 , 2 ) = -2+1-2+1+1-2+1-2 = -3

𝑆1 C 𝑆2 -2 ( 1,

Alinhamento 2 T G C - - A A T T - C G C A - T A 1 -2 1 -2 -2 1 -2 1 -2 2 ) = -2+1-2+1-2-2+1-2 = -8

Figura 9. Exemplo de alinhamentos possíveis com pontuação.

2.6.

Análise das Sequências biológicas alinhadas Para a Biologia Molecular, o mais importante é obter o alinhamento de maior inferência biológica. Para isso, quando se comparam as sequências biológicas, verifica-se dois fatores: Se há evidência de ancestral comum e se as divergências poderiam ocorrer mediante mutações ou seleção natural. No processo de mutação são considerados a substituição, inserção ou eliminação de caracteres. No processo de seleção natural, são averiguadas quais mutações foram potencializadas em prejuízo de outras. Contudo, eventos como inversões e transposições não costumam ser detectados por algoritmos tradicionais. Existem ferramentas que geram matrizes de distâncias, necessárias à criação de árvores filogenéticas. Estes algoritmos comparam os genes de espécies em estudo, dispondo as pontuações de cada um numa tabela de pontuação, de modo que as bases nitrogenadas iguais possuem pontuação (+2), e diferentes, pontuação (-1), para deslocamentos não se ocorre pontuação.

7

Figura 10. Exemplo de comparação de genes.

De um ponto de vista biológico, mutações entre bases possuem probabilidades diferentes, devido à composição das mesmas. Mudanças de bases da mesma classe podem ser chamadas de transições, e são mais frequentes que mudanças de bases de classes distintas, as quais chamadas de transversões. As bases nitrogenadas são divididas entre purinas (Adenina e Guanina) e piridinas (Citosina e Timina).

Figura 11. Tabela de pontuação de Transições e Transversões.

Diante de alinhamentos múltiplos, a escolha da função torna-se menos relevante, pois as comparações entre sequências geralmente representam espécies distintas.

2.6.1. Distancia evolutiva A distância evolutiva entre um par de sequências pode ser estimada de várias maneiras, com a forma mais simples sendo distância-p, isto é, a fração dos sítios em que as duas sequências diferem. Infelizmente este tipo de métrica de distância subestima a real quantidade de evolução, já que não leva em conta a possibilidade de múltiplas substituições em um mesmo local. Os chamados métodos de 'Evolução Mínima’ (ME, Minimum Evolution), que levam em conta a possibilidade de que tenham ocorrido múltiplas substituições na mesma posição das sequências. O problema é que esta classe de métodos poder ser 8

computacionalmente muito dispendiosa e como os métodos de distância são, normalmente, usados pela sua rapidez, nem sempre compensa empregar os métodos de ME. Somente mutações ocorridas de forma a não provocar a extinção da espécie descendente são aceitas. Para isso utilizamos um processo de verificação chamado PAM (Point Accepted Mutation) [DAYHOFF, 1978], que se refere a uma matriz gerada entre duas sequências de homólogas.

2.6.2. Distancia de edição A distância de edição é dada pelo número mínimo de operações de edição, como inserção, substituição ou remoção, necessárias para transformar uma sequência em outra. As técnicas de distância de edição mais conhecidas são Levenshtein [HIRSCHBERG, 1997] e Hamming [Hamming, 1980]. A técnica de Levenshtein pode ser utilizado em strings de tamanhos diferentes utilizando um cálculo de custo para as três operações citadas, já a técnica de Hamming somente pode ser utilizado em cadeias de strings que possuam o mesmo tamanho.

3.

Algoritmos para alinhamento de sequencias Apresentaremos neste capítulo algoritmos básicos que possuem duas etapas, na primeira, calcula-se as distancias e gera-se a matriz de pontuação, no segundo determina-se o alinhamento ótimo que corresponde ao melhor alinhamento, ou a pontuação mínima aceita. Além disso, é dado enfoque nos algoritmos Needman-Wunsh [Needlman & Wunsch, 1970] e Smith-Waterman [Smith & Waterman, 1981], que utilizam método de programação dinâmica para realizar os alinhamentos.

3.1.

Algoritmo de alinhamento de pares de sequência (APS) A entrada de valores contam com duas sequências onde s pertence a ∑ e t pertence a ∑ , de tamanhos, respectivamente iguais a m e n, como pode ser visto na Figura 14 e 15.

Figura 12. Notação Matemática

9

Figura 13. Matriz de pontuação. [Brito, 2003].

Na primeira etapa deste algoritmo, calcula-se a distância gerando a tabela de pontuação conforme o pseudocódigo apresentado na Figura 16. Algoritmo - Dist(seq, seq2) Entrada:

Duas sequências s e t, com |s|=m e |t|=n. Saída: Uma matriz a = ( a [i, j] ) com a [i, j] = d(s[1 . . i], t[1 . . j]). 1. m ← |s|; n ← |t|; a [0, 0] ← 0; 2. para j = 1, . . . , n faça a 3. a [0, j] ← a [0, j − 1] + c(“-”,seq2 [j]); 4. para i = 1, . . . , m faça 5. a[i, 0] ← a[i − 1, 0] + c(s[i], “-”); 6. para j = 1, . . . , n faça 7. a[i, j] ← a[i − 1, j] + c(s[i], “-”); 8. se a[i, j] > a[i − 1, j − 1] + c(s[i], t[j]) então 9. a[i, j] ← a[i − 1, j − 1] + c(s[i], t[j]); 10. se a[i, j] > a[i, j − 1] + c(“-”,t[j]) então 11. a[i, j] ← a[i, j − 1] + c(“-”,t[j]); 12. Devolva a; Figura 14. Algoritmo de geração da tabela de pontuação.

Para as sequências s e t , uma matriz a de dimensões (𝑚 + 1)×(𝑛 + 1), indexada por {0, … , 𝑚} e {0, … , 𝑛}, é preenchida com as pontuações de alinhamentos ótimos de prefixos de s com prefixos de t, de forma que a posição (𝑖, 𝑗) de a contenha a pontuação de um alinhamento ótimo de [1. . 𝑖] 𝑒 𝑡[1. . 𝑗] , isto é, de modo que 𝑎[𝑖, 𝑗] 𝑑( [1. . 𝑖], 𝑡[1. . 𝑗]), para 0 ≤ 𝑖 ≤ 𝑚 𝑒 0 ≤ 𝑗 ≤ 𝑛. A distância 𝑑( , 𝑡) = 𝑑( [1. . 𝑚], 𝑡[1. . 𝑛]) está na posição 𝑎[𝑚, 𝑛].

10

Algoritmo - Alinha(a, s, t) Entrada: Duas seqüências s e t e a matriz a devolvida por Dist(s, t). Saída: Um alinhamento entre s e t de pontuação mínima. 1. m ← |s|; n ← |t|; 2. se n = 0 então 3.

Devolva os caracteres de t alinhados a espaços em s;

4. se m = 0 então 5.

Devolva os caracteres de s alinhados a espaços em t;

6. se a [m, n] = a [m − 1, n] + c ( s [m], “-”) então 7.

Devolva ( Alinha(a, s[ 1 . . m−1], t ) :

“−“ t[n]

)

8. se a [m, n] = a[ m − 1, n – 1 ] + c( s[m], t[n] ) então 9.

Devolva ( Alinha (a, s[1..m–1], t[1..n–1] ) :

10.

se a[m, n] = a [m, n−1] + c( “-”,t[n]) então

11.

Devolva(Alinha(a, s, t[1..n−1]) :

s[m]

𝑡[𝑛]

)

[𝑚] ) "−"

12. Figura 15. Algoritmo de alinhamento par-a-par.

3.2.

Algoritmo de Needleman-Wunsch – Alinhamento Global Existem algumas outras técnicas similares, com alteração apenas na criação da matriz de pontuação, como, por exemplo, o algoritmo de Needleman & Wunsch [Needlman & Wunsch, 1970] que utiliza programação dinâmica para realizar o alinhamento global. Este algoritmo utiliza uma tabela bidimensional com uma sequência da esquerda para cima, podendo chegar em cada célula da tabela de 3 maneiras: 

A partir da célula de cima, que corresponde a um alinhamento do caractere esquerdo com uma lacuna (𝑦1 alinha com lacuna)



A partir da célula da esquerda, que corresponde ao alinhamento do caractere de cima com uma lacuna (𝑥1 alinha com lacuna).



A partir da célula diagonal esquerda-cima, que corresponde ao alinhamento dos caracteres da esquerda e de cima (𝑥1 alinha com 𝑦1 ).

Considerando as sequências 𝑆1 = GCCCTAGCG e S2 = GCGCAATG, teríamos a tabela da Figura 18.

11

Figura 16. Exemplo da Tabela Needleman-Wunsch. Fonte: [Needlman & Wunsch, 1970]

A primeira etapa do algoritmo, conforme citado anteriormente, gera-se a tabela de pontuação, preenchendo as células da esquerda para a direita e de cima para baixo conforme pode ser visto no pseudocódigo da Figura 19. Algoritmo de Needleman-Wunsch Part-1 1. For i=0) to length(A) 2. F(i,0) ← d*i 3. for j=0 to length(B)-1 4. F(0,j) ← d*j 5. for i=1 to length(A) 6. for j = 1 to length(B) 7. { 8. Choice1 ← F(i-1,j-1) + S(A(i-1), B(j-1)) 9. Choice2 ← F(i-1, j) + d 10. Choice3 ← F(i, j-1) + d 11. F(i,j) ← max(Choice1, Choice2, Choice3) 12. } Figura 17. Pseudocódigo Geração de tabela do algoritmo Needleman-Wunsch. Fonte: [Needlman & Wunsch, 1970]

Após a matriz F ser calculada, o elemento na posição do canto inferior direito da tabela é considerado a pontuação máxima para qualquer alinhamento. O algoritmo inicia a verificação da direita inferior, em direção a esquerda superior da tabela, realizando comparações entre as 3 possibilidades, nomeadas como “Choice1”, “Choice2”e “Choice3”.

12

Algoritmo de Needleman-Wunsch Part-2 1. AlignmentA ← "" 2. AlignmentB ← "" 3. i ← length(A) 4. j ← length(B) 5. while (i > 0 AND j > 0) 6. { 7. Score ← F(i,j) 8. ScoreDiag ← F(i - 1, j - 1) 9. ScoreUp ← F(i, j - 1) 10. ScoreLeft ← F(i - 1, j) 11. if (Score == ScoreDiag + S(A(i-1), B(j-1))) 12. { 13. AlignmentA ← A(i-1) + AlignmentA 14. AlignmentB ← B(j-1) + AlignmentB 15. i ← i – 1 16. j ← j – 1 17. } 18. else if (Score == ScoreLeft + d) 19. { 20. AlignmentA ← A(i-1) + AlignmentA 21. AlignmentB ← "-" + AlignmentB 22. i ← i – 1 23. } 24. } 25. while (i > 0) 26. { 27. AlignmentA ← A(i-1) + AlignmentA 28. AlignmentB ← "-" + AlignmentB 29. i ← i – 1 30. } 31. while (j > 0) 32. { 33. AlignmentA ← "-" + AlignmentA 34. AlignmentB ← B(j-1) + AlignmentB 35. j ← j – 1 36. } Figura 18. Pseudocódigo do algoritmo Needleman-Wunsch. Fonte: [Needlman & Wunsch, 1970]

3.3.

Algoritmo de Smith & Waterman – Alinhamento local O algoritmo de Smith & Waterman [Smith & Waterman, 1981] é uma variação do algoritmo de Needleman & Wunsch [Needlman & Wunsch, 1970] utilizado para realizar alinhamento local. Ele busca por regiões locais semelhantes, sem varrer todo seu comprimento. A principal diferença entre esses algoritmos é que as células da matriz com pontuação negativa são substituídas por valores zero, o que torna alinhamentos locais mais visíveis. O processo inicia na célula da matriz com pontuação mais alta e varre toda a tabela até encontrar uma célula com pontuação zero. Considere o exemplo 𝑆1 = GCCCTAGCG e S2 = GCGCAATG e como seria varrida a tabela de pontuação na Figura 21. 13

Figura 19. Exemplo de uma Tabela de Smith-Waterman. Fonte:[SMITH & WATERMAN ,1981]

Durante a geração da tabela de pontuação, fica mais claro a diferença entre os algoritmos de Smith-Waterman[Smith & Waterman, 1981] e Needleman-Wunsch [Needlman & Wunsch, 1970], o primeiro, na fase de inicialização, preenche a primeira linha e a primeira coluna da tabela com 0s e os ponteiros da primeira linha e da primeira coluna são nulos. Após preenchida a tabela, caso ocorra uma pontuação negativa, substitui-se por 0. Também deve-se manter o controle de qual célula tem a pontuação mais alta. Na última parte do algoritmo, inicia-se com a célula com maior pontuação e se traça um caminho até chegar a uma célula com pontuação 0, caso contrário, o rastreamento funcionaria como o algoritmo de Needleman-Wunsch [Needlman & Wunsch, 1970].

14

Algoritmo de Smith-Waterman Uma matriz

é construída como se segue:

1. (i, 0) = 0, 0