b'\n_START_ARTICLE_\nAlgoritmo de Smith-Waterman\n_START_SECTION_\nPano de fundo\n_START_PARAGRAPH_\nO algoritmo foi proposto pela primeira vez por Temple F. Smith e Michael S. Waterman em 1981. Como o Algoritmo Needleman-Wunsch, do qual \xc3\xa9 uma varia\xc3\xa7\xc3\xa3o, o Smith-Waterman \xc3\xa9 um algoritmo de programa\xc3\xa7\xc3\xa3o din\xc3\xa2mica. Como tal, tem a propriedade desej\xc3\xa1vel de que \xc3\xa9 garantido encontrar o alinhamento local \xc3\xb3timo com rela\xc3\xa7\xc3\xa3o ao sistema de pontua\xc3\xa7\xc3\xa3o a ser utilizado (o que inclui a matriz de substitui\xc3\xa7\xc3\xa3o e o esquema de escore para lacunas). A principal diferen\xc3\xa7a para o algoritmo Needleman-Wunsch \xc3\xa9 que as c\xc3\xa9lulas da matriz com pontua\xc3\xa7\xc3\xa3o negativa tem seus valores definidos para zero, que torna os alinhamentos locais (pontuados assim positivamente) vis\xc3\xadveis. O processo de Backtracking (Retrocesso) come\xc3\xa7a na c\xc3\xa9lula da matriz de pontua\xc3\xa7\xc3\xa3o mais alta e continua at\xc3\xa9 que uma c\xc3\xa9lula com pontua\xc3\xa7\xc3\xa3o zero seja encontrada, produzindo o alinhamento com a maior pontua\xc3\xa7\xc3\xa3o local. N\xc3\xa3o se implementa o algoritmo como descrito porque melhores alternativas est\xc3\xa3o agora dispon\xc3\xadveis que t\xc3\xaam melhor dimensionamento e s\xc3\xa3o mais precisas.\n_START_SECTION_\nMotiva\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nUma motiva\xc3\xa7\xc3\xa3o para o alinhamento local \xc3\xa9 a dificuldade de obten\xc3\xa7\xc3\xa3o de alinhamentos corretos em regi\xc3\xb5es de baixa similaridade entre seq\xc3\xbc\xc3\xaancias biol\xc3\xb3gicas distantemente relacionadas, porque as muta\xc3\xa7\xc3\xb5es j\xc3\xa1 somaram muito "ru\xc3\xaddo" ao longo do tempo evolutivo para permitir uma compara\xc3\xa7\xc3\xa3o significativa dessas regi\xc3\xb5es. Alinhamentos locais evitam tais regi\xc3\xb5es completamente e se concentram naquelas com uma pontua\xc3\xa7\xc3\xa3o positiva, ou seja, aquelas com um sinal de similaridade evolutivo conservado. Um pr\xc3\xa9-requisito para o alinhamento local \xc3\xa9 uma pontua\xc3\xa7\xc3\xa3o de expectativa negativa. A pontua\xc3\xa7\xc3\xa3o de expectativa \xc3\xa9 definida como a pontua\xc3\xa7\xc3\xa3o m\xc3\xa9dia que o sistema de pontua\xc3\xa7\xc3\xa3o (matriz de substitui\xc3\xa7\xc3\xa3o e penalidade para lacunas) daria para uma seq\xc3\xbc\xc3\xaancia aleat\xc3\xb3ria._NEWLINE_Outra motiva\xc3\xa7\xc3\xa3o para a utiliza\xc3\xa7\xc3\xa3o de alinhamentos locais \xc3\xa9 que h\xc3\xa1 um modelo de estat\xc3\xadstica fi\xc3\xa1vel (desenvolvido por Karlin e Altschul) para alinhamentos locais \xc3\xb3timos. O alinhamento das seq\xc3\xbc\xc3\xaancias independentes tende a produzir \xc3\xb3timas pontua\xc3\xa7\xc3\xb5es no alinhamento local que seguem uma distribui\xc3\xa7\xc3\xa3o de valor extremo. Essa propriedade permite que programas produzam um valor de expectativa para o alinhamento local \xc3\xb3timo de duas sequ\xc3\xaancias, que \xc3\xa9 uma medida de quantas vezes duas sequ\xc3\xaancias n\xc3\xa3o relacionadas produziriam um alinhamento local \xc3\xb3timo cuja pontua\xc3\xa7\xc3\xa3o fosse maior ou igual \xc3\xa0 pontua\xc3\xa7\xc3\xa3o observada. Valores de expectativa muito baixos indicam que as duas sequ\xc3\xaancias em quest\xc3\xa3o podem ser hom\xc3\xb3logas, o que significa que elas podem compartilhar um ancestral comum._NEWLINE_O algoritmo Smith-Waterman \xc3\xa9 bastante exigente em termos de tempo: alinhar duas seq\xc3\xbc\xc3\xaancias de comprimentos m e n, exige tempo de O(mn). As pontua\xc3\xa7\xc3\xb5es de similaridade local de Smith-Waterman podem ser calculadas com espa\xc3\xa7o O(m) (linear), mas algoritmos ing\xc3\xaanuos para produzir o alinhamento requerem o espa\xc3\xa7o O(mn). Uma estrat\xc3\xa9gia de alinhamento de espa\xc3\xa7o linear foi descrita. O BLAST e o FASTA reduzem o tempo necess\xc3\xa1rio para identificar regi\xc3\xb5es conservadas usando estrat\xc3\xa9gias de pesquisa r\xc3\xa1pida._NEWLINE_Uma implementa\xc3\xa7\xc3\xa3o do Algoritmo Smith-Waterman, SSEARCH, est\xc3\xa1 dispon\xc3\xadvel no pacote de an\xc3\xa1lise de seq\xc3\xbc\xc3\xaancia FASTA em . Esta implementa\xc3\xa7\xc3\xa3o inclui c\xc3\xb3digo Altivec acelerado para processadores PowerPC G4 e G5 que aceleram as compara\xc3\xa7\xc3\xb5es de 10 a 20 vezes, usando uma modifica\xc3\xa7\xc3\xa3o da abordagem de Wozniak, 1997, e uma vetoriza\xc3\xa7\xc3\xa3o SSE2 desenvolvida por Farrar tornando as pesquisas \xc3\xb3timas em banco de dados de seq\xc3\xbc\xc3\xaancia de prote\xc3\xadna bastante pr\xc3\xa1ticas.'