Global entre duas seqüências s e T. Calcule a similaridade global entre as seqüências: agtcgtgac e cgtagtccgtgat. Use pontuação match=1, mismatch=0, gap= Faça primeiro na mão e depois confira com a sua planilha



Baixar 8.17 Kb.
Encontro04.06.2018
Tamanho8.17 Kb.

Universidade Estadual de Campinas
Disciplina: Biologia Computacional – MO640
Assunto: ata de resoluções sobre a aula de 2008-08-14


  1. Crie uma planilha eletrônica que construa a matriz necessária para calcular a similaridade global entre duas seqüências S e T.

  2. Calcule a similaridade global entre as seqüências: AGTCGTGAC e CGTAGTCCGTGAT. Use pontuação match=1, mismatch=0, gap=-2. Faça primeiro na mão e depois confira com a sua planilha.

(seguem anexas duas versões de spreadsheets)



  1. Uma subseqüência de uma seqüência S de caracteres é uma seqüência que pode ser obtida a partir de S pela remoção de zero ou mais caracteres. Dadas duas seqüências S e T, mostre como é possível encontrar uma seqüência que seja subseqüência tanto de S como de T e tenha comprimento máximo, utilizando o algoritmo de comparação global visto em aula. Que pontuação deve ser usada?

R: Pontuação deve ser: match = 1, gap = 0, mismatch ≤ 0.

Devemos escolher uma pontuação que monte um alinhamento de forma que os caracteres iguais estejam sempre alinhados e os outros fiquem alinhados com branco.

Algo do tipo:

s = A – – T – T A G ; m = 5


t = – G T T A T A – ; n = 6

Desse modo, se o valor para alinhamento entre caracteres iguais (match) for igual a 1, estaremos pontuando de forma positiva o alinhamento de caracteres iguais. Se para o alinhamento com caracteres em “branco” (gap) atribuirmos o valor zero, isso quer dizer que estaremos ignorando (não penalizando a similaridade) se “branco” aparece no início de qualquer uma das seqüências.


Então, se utilizarmos a pontuação match = 1, gap = 0 e mismatch ≤ 0, temos que o elemento da matriz de similaridade da última linha e última coluna ( a[m,n] ) sempre conterá o valor do número de caracteres iguais entre as duas cadeias comparadas e sempre conterá o maior valor da matriz inteira; desse modo não estaremos penalizando a similaridade se “branco” aparecer no final de qualquer uma das seqüências (pois estamos calculando a similaridade entre uma cadeia inteira e o prefixo da outra que é nesse caso uma cadeia inteira). Além disso, os valores da matriz de similaridade a[i][j] não se alteram para match = 1, gap = 0 e mismatch ≤ 0.
Para encontrar a subseqüência máxima entre duas seqüências é necessário alterar o algoritmo de alinhamento para escrever somente quando um caractere é igual ao outro e ignorar os outros casos entretanto mantendo as chamadas recursivas. Isto dá origem ao algoritmo que descreve a maior subseqüência, descrito abaixo:

Algoritmo MaiorSubsequência:

Entradas: Inteiro i, Inteiro j, tamanho
Saída: vetor SubsequenciaMáxima[], tamanho

se i = 0 e j = 0
então
tamanho  0
senão se i > 0 e a[ i, j ] = a[ i-1, j ] + 0 // a[ i, j ] = a[ i-1, j ] + g
então
MaiorSubsequência ( i -1, j, tamanho )
senão se i > 0 e j >0 e a[ i, j ] = a[ i-1, j-1] + p(i,j)
então
MaiorSubsequência ( i -1, j -1, tamanho )
tamanho  tamanho +1
SubsequenciaMáxima[ tamanho ]  s[ i ]
senão // j > 0 e a[ i, j ] = a[ i, j-1 ] + 0
MaiorSubsequência ( i, j-1, tamanho )
fim-se
fim-se
fim-se



Função
p
Entradas:
inteiro i, inteiro j
Saída:
retorna inteiro //retorna o tipo do valor de match e mismatch

se s[i] = t[j]
então
retorna
1 //retorna match = 1
senão
retorna
0 // retorna mismatch ≤ 0
fim-se


obs:
considere:
s[] - o vetor que descreve a seqüência s
SubsequenciaMáxima[] - o vetor que descreve a maior subseqüência entre as seqüências s e t.
a[i,j] - matriz de similaridade global previamente calculado.




©aneste.org 2017
enviar mensagem

    Página principal