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.


Compartilhe com seus amigos:


©aneste.org 2020
enviar mensagem

    Página principal
Universidade federal
Prefeitura municipal
santa catarina
universidade federal
terapia intensiva
Excelentíssimo senhor
minas gerais
união acórdãos
Universidade estadual
prefeitura municipal
pregão presencial
reunião ordinária
educaçÃo universidade
público federal
outras providências
ensino superior
ensino fundamental
federal rural
Palavras chave
Colégio pedro
ministério público
senhor doutor
Dispõe sobre
Serviço público
Ministério público
língua portuguesa
Relatório técnico
conselho nacional
técnico científico
Concurso público
educaçÃo física
pregão eletrônico
consentimento informado
recursos humanos
ensino médio
concurso público
Curriculum vitae
Atividade física
sujeito passivo
ciências biológicas
científico período
Sociedade brasileira
desenvolvimento rural
catarina centro
física adaptada
Conselho nacional
espírito santo
direitos humanos
Memorial descritivo
conselho municipal
campina grande