Programação para as
Ciências Experimentais
2006/7
Teórica 8
Ludwig Krippahl, 2007
Na aula de hoje...





Estruturas.
Listas.
Ficheiros, leitura e escrita simples.
Comparação de sequências.
Exemplo de uma função recursiva.
Ludwig Krippahl, 2007
2
Estruturas



Vectores e matrizes guardam valores
de um só tipo.
Estruturas podem guardar valores de
vários tipos.
Sintaxe:
•
variável.campo
Ludwig Krippahl, 2007
3
Estruturas

Exemplo:
octave:7> prato.nome="filetes";
octave:8> prato.preco=12.5;
octave:9> prato.pedidos=[10,2,3,5,9,5,9];
octave:10> prato
prato =
{
nome = filetes
pedidos =
10 2 3 5 9 5 9
preco = 12.500
}
Ludwig Krippahl, 2007
4
Estruturas

Recapitulando
•
•
•
•
nome_da_variavel.campo1=val1
nome_da_variavel.campo2=val2
nome_da_variavel.campo2=val2
Cada campo pode ter um valor de tipo
diferente, incluindo ser outra estrutura.
Ludwig Krippahl, 2007
5
Estruturas

Estrutura de estrutura...
octave:13> cliente.nome="Vitor Meireles";
octave:14> cliente.prato=prato
cliente =
{
nome = Vitor Meireles
prato =
{
nome = filetes
pedidos =
10 2 3 5 9 5 9
preco = 12.500
}
}
Ludwig Krippahl, 2007
6
Listas

Não podemos criar vectores de
estruturas:
octave:15> v=[prato,cliente]
error: octave_base_value::matrix_value(): wrong
type argument `struct'
error: evaluating assignment expression near line
15, column 2
Ludwig Krippahl, 2007
7
Listas



Para agrupar estruturas ou variáveis de
vários tipos temos que criar uma lista.
Usamos a função list, que recebe em
cada argumento um valor e devolve
uma lista com esses valores.
Ex:
octave:17> l=list(1,"abc",prato)
Ludwig Krippahl, 2007
8
Listas
l=
(
[1] = 1
1º elemento: escalar
[2] = abc
2º elemento: string
[3] =
3º elemento: estrutura
{
nome = filetes
pedidos =
10 2 3 5 9 5 9
preco = 12.500
}
)
Ludwig Krippahl, 2007
9
Listas

Podemos criar a lista
incrementalmente, partindo da lista
vazia:
•

l=list;
E acrescentando um valor de cada vez:
•
•
•
l=append(l,1)
l=append(l,"abc")
l=append(l,prato)
Ludwig Krippahl, 2007
10
Listas

append(x,y)
•
Devolve a lista resultante de acrescentar y
no final de x. Se y for uma lista acrescenta
todos os elementos de y no final de x.
Ludwig Krippahl, 2007
11
Listas

append(x,y)
octave:21> l=list
l = ()
octave:22> l=append(l,1)
l=
(
[1] = 1
)
octave:23> l=append(l,"abc")
l=
(
[1] = 1
[2] = abc
)
Ludwig Krippahl, 2007
12
Listas

Aceder a um elemento da lista:
•
como um vector ou usar a função nth, que devolve
o n-ésimo elemento da lista.
octave:42> l(1:2)
ans =
(
[1] = 1
[2] = abc
)
octave:43> nth(l,2)
ans = abc
Ludwig Krippahl, 2007
13
Listas


Aceder a um elemento da lista:
•
como um vector ou usar a função nth, que
devolve o n-ésimo elemento da lista.
Atenção:
•
•
Ao aceder à lista como um vector o
resultado é uma lista. Ex: l(1) não é o
primeiro elemento, mas uma lista com o
primeiro elemento.
Para obter o elemento n usar nth(l,n).
Ludwig Krippahl, 2007
14
Ficheiros


Para aceder a um ficheiro temos que o
identificar com uma estrutura com
informação acerca do ficheiro.
Usamos a função fopen para abrir o
ficheiro (e obter o identificador), fclose
para fechar e deixar livre o ficheiro
para outras aplicações.
Ludwig Krippahl, 2007
15
Ficheiros

fopen(nome,modo [, arquitectura])
•
normalmente usamos só os primeiros dois
argumentos:
octave:7> teste=fopen("teste.txt","w")
teste =
{
id = 3
name = teste.txt
mode = w
arch = native
status = 1
}
Ludwig Krippahl, 2007
16
Ficheiros

fopen(nome, modo, arquitectura)
•
normalmente usamos só os primeiros dois
argumentos:
octave:7> teste=fopen("teste.txt","w")
• Guarda na variável teste a estrutura que
identifica o ficheiro.
Ludwig Krippahl, 2007
17
Ficheiros

fopen(nome, modo, arquitectura)
•
normalmente usamos só os primeiros dois
argumentos:
octave:7> teste=fopen("teste.txt","w")
• Guarda na variável teste a estrutura que
identifica o ficheiro.
• No final fechamos o ficheiro:
octave:8> fclose(teste)
ans = 0
Ludwig Krippahl, 2007
18
Ficheiros

fopen(“teste.txt”, “w”)
•
•
•
•
Modo “w”, write, para escrita. Apaga o
conteúdo original.
Modo “r”, read, para leitura.
Modo “a”, append, para acrescentar ao
ficheiro. Preserva o conteúdo original
(Ver outros modos no manual)
Ludwig Krippahl, 2007
19
Ficheiros

Ler dados de um ficheiro:
•
•
•
•
fgetl( identificador, comprimento)
Lê uma linha do ficheiro identificado, ou o
número de caracteres no comprimento.
Se o comprimento é omitido, lê todos os
caracteres até ao final da linha.
Se não há mais linhas devolve -1.
Ludwig Krippahl, 2007
20
Ficheiros

Sabemos que o ficheiro chegou ao fim
com a função feof:
•
feof( identificador )
•
Ludwig Krippahl, 2007
Devolve true se o ficheiro estiver no fim.
21
Exemplo: ler sequências de
proteínas.
O formato FASTA é um formato de
texto para guardar sequências.
 As linhas começadas por “>”
identificam a molécula (proteína, RNA,
ou DNA):
>UniProt/Swiss-Prot|P00273|DE....

Ludwig Krippahl, 2007
22
Exemplo: ler sequências de
proteínas.


O formato FASTA é um formato de
texto para guardar sequências.
As restantes linhas contêm a
sequência:
ALSAADAGLLAQSWAPVFANSDANGASF...
RDVSSRIFARLNEFVSNAADAGKMGSML...
APAADAAWNSLFGLIISALQSAGK
Ludwig Krippahl, 2007
23
Exemplo: ler sequências de
proteínas.


O formato FASTA é um formato de
texto para guardar sequências.
Como no máximo este formato usa 80
caracteres por linha a sequência pode
estar partida em várias linhas.
ALSAADAGLLAQSWAPVFANSDANGASF...
RDVSSRIFARLNEFVSNAADAGKMGSML...
APAADAAWNSLFGLIISALQSAGK
Ludwig Krippahl, 2007
24
Exemplo: ler sequências de
proteínas.

Função lefasta(nome)
•
•
Lê o ficheiro cujo nome é fornecido e
devolve uma lista de estruturas.
Em cada estrutura tem dois campos, id,
com a identificação da proteína, e seq, com
a sequência da proteína.
Ludwig Krippahl, 2007
25
Exemplo: ler sequências de
proteínas.
function l=lefasta(nome)
id=fopen(nome,”r”); Abre o ficheiro e
guarda o identificador
l=list;
(Ciclo de leitura do ficheiro)
fclose(id);
endfunction
Ludwig Krippahl, 2007
26
Exemplo: ler sequências de
proteínas.
function l=lefasta(nome)
id=fopen(nome);
l=list;
Cria uma lista vazia
(Ciclo de leitura do ficheiro)
fclose(id);
endfunction
Ludwig Krippahl, 2007
27
Exemplo: ler sequências de
proteínas.
function l=lefasta(nome)
id=fopen(nome);
l=list;
(Ciclo de leitura do ficheiro)
fclose(id);
endfunction
Ludwig Krippahl, 2007
Depois de ler o ficheiro,
fecha e termina a
função
28
Exemplo: ler sequências de
proteínas.
r.seq='';
while !feof(id)
s=fgetl(id);
if strcmp(s(1),'>')
if !strcmp(r.seq,'')
l=append(l,r);
endif
r.id=s;
r.seq='';
else r.seq=[r.seq,s];
endif
endwhile
if !strcmp(r.seq,'')
l=append(l,r);
endif
Ludwig Krippahl, 2007
Ciclo enquanto o
ficheiro não chegou ao
fim.
29
Exemplo: ler sequências de
proteínas.
r.seq='';
while !feof(id)
s=fgetl(id);
if strcmp(s(1),'>')
if !strcmp(r.seq,'')
l=append(l,r);
endif
r.id=s;
r.seq='';
else r.seq=[r.seq,s];
endif
endwhile
if !strcmp(r.seq,'')
l=append(l,r);
endif
Ludwig Krippahl, 2007
Lê uma linha e compara
o primeiro caracter com
“>”
(quer dizer que
encontrou uma proteína
nova)
30
Exemplo: ler sequências de
proteínas.
r.seq='';
while !feof(id)
s=fgetl(id);
if strcmp(s(1),'>')
if !strcmp(r.seq,'')
l=append(l,r);
endif
r.id=s;
r.seq='';
else r.seq=[r.seq,s];
endif
endwhile
if !strcmp(r.seq,'')
l=append(l,r);
endif
Ludwig Krippahl, 2007
Se há uma sequência
guardada, então
acrescenta r à lista l
É por isto que a
sequência em r começa
vazia
31
Exemplo: ler sequências de
proteínas.
r.seq='';
while !feof(id)
s=fgetl(id);
if strcmp(s(1),'>')
if !strcmp(r.seq,'')
l=append(l,r);
endif
r.id=s;
r.seq='';
else r.seq=[r.seq,s];
endif
endwhile
if !strcmp(r.seq,'')
l=append(l,r);
endif
Ludwig Krippahl, 2007
Quando encontra nova
proteína guarda o
identificador da
proteína e limpa a
sequência.
32
Exemplo: ler sequências de
proteínas.
r.seq='';
while !feof(id)
s=fgetl(id);
if strcmp(s(1),'>')
if !strcmp(r.seq,'')
l=append(l,r);
endif
r.id=s;
r.seq='';
else r.seq=[r.seq,s];
endif
endwhile
if !strcmp(r.seq,'')
l=append(l,r);
endif
Ludwig Krippahl, 2007
Se não é uma proteína
nova então é outra
linha da sequência,
para juntar à sequência
lida até agora
33
Exemplo: ler sequências de
proteínas.
r.seq='';
while !feof(id)
s=fgetl(id);
if strcmp(s(1),'>')
if !strcmp(r.seq,'')
l=append(l,r);
endif
r.id=s;
r.seq='';
else r.seq=[r.seq,s];
endif
endwhile
if !strcmp(r.seq,'')
l=append(l,r);
endif
Ludwig Krippahl, 2007
No final do ciclo
acrescentar a última
proteína lida, se houver
34
Exemplo: centros Fe S
Ludwig Krippahl, 2007
35
Desulforedoxin, 1DXG
Dímero
Ludwig Krippahl, 2007
36
Ludwig Krippahl, 2007
37
Ludwig Krippahl, 2007
38
Ludwig Krippahl, 2007
39
Exemplo: centros Fe S
>...Desulforedoxin
ANEGDVYKCELCGQVVKVLEEGGGTLV
CCGEDMVKQ



Padrão do centro:
...C-[até 4]-C- ... -C-[até 4]-C-...
Ludwig Krippahl, 2007
40
Exemplo: centros Fe S

Para fazer na aula prática:
•
•
Função vec=contafes(lista)
A partir da lista de estruturas com seq, a
sequência de cada proteína, devolve o
número estimado de centros de Fe-S
contando as cisteínas no padrão:
...C-[até 4]-C- ... -C-[até 4]-C-...
Ludwig Krippahl, 2007
41
Alinhar Sequências:
Needleman-Wunsch


Saul Needleman e Christian Wunsch
A general method applicable to the
search for similarities in the amino acid
sequence of two proteins, J Mol Biol.
48(3):443-53.
Ludwig Krippahl, 2007
42
Alinhar Sequências:
Needleman-Wunsch


De duas sequências:
• ABBCD e ABCED
Obter o alinhamento:
ABBC-D
| || |
A-BCED
Ludwig Krippahl, 2007
43
Alinhar Sequências:
Needleman-Wunsch

Duas sequências:

Construir uma matriz com tantas linhas
quanto o comprimento da primeira e
colunas quanto o comprimento da
segunda (todas as combinações)
• Exemplo: ABBCD e ABCED
Ludwig Krippahl, 2007
44
Alinhar Sequências:
Needleman-Wunsch

Matriz
A
A
B
B
C
D
Ludwig Krippahl, 2007
B
0
0
0
0
0
C
0
0
0
0
0
E
0
0
0
0
0
D
0
0
0
0
0
0
0
0
0
0
45
Alinhar Sequências:
Needleman-Wunsch



Em cada célula contamos 1 se os
elementos da sequência forem iguais.
E somamos o máximo obtido por alinhar
os elementos anteriores.
Regra: Cada célula é o máximo da
matriz acima e à esquerda, +1 se os
elementos forem iguais.
Ludwig Krippahl, 2007
46
Alinhar Sequências:
Needleman-Wunsch

Máximo da matriz acima e à esquerda,
+1 se os elementos forem iguais.
• Alinhar o 1º elemento com todos os outros
A
A
B
B
C
D
Ludwig Krippahl, 2007
B
1
C
0
E
0
D
0
0
47
Alinhar Sequências:
Needleman-Wunsch

Máximo da matriz acima e à esquerda,
+1 se os elementos forem iguais.
• Alinhar o 2º elemento com todos os outros
A
A
B
B
C
D
Ludwig Krippahl, 2007
B
1
0
C
0
1
E
0
0
D
0
0
0
0
48
Alinhar Sequências:
Needleman-Wunsch

Máximo da matriz acima e à esquerda,
+1 se os elementos forem iguais.
• Somar em o melhor alinhamento anterior
A
A
B
B
C
D
Ludwig Krippahl, 2007
B
1
0
C
0
2
E
0
1
D
0
1
0
1
49
Alinhar Sequências:
Needleman-Wunsch

Máximo da matriz acima e à esquerda,
+1 se os elementos forem iguais.
• Somar em o melhor alinhamento anterior
A
A
B
B
C
D
Ludwig Krippahl, 2007
B
1
0
0
0
0
C
0
2
2
1
1
E
0
1
2
3
2
D
0
1
2
2
3
0
1
2
2
4
50
Alinhar Sequências:
Needleman-Wunsch

O alinhamento é dado pelo máximo,
depois o máximo das sub-matrizes à
esquerda e acima.
Ludwig Krippahl, 2007
51
Alinhar Sequências:
Needleman-Wunsch

Máximo, depois o máximo das submatrizes à esquerda e acima.
A
A
B
B
C
D
Ludwig Krippahl, 2007
B
1
0
0
0
0
C
0
2
2
1
1
E
0
1
2
3
2
D
|
D
D
0
1
2
2
3
0
1
2
2
4
52
Alinhar Sequências:
Needleman-Wunsch

Máximo, depois o máximo das submatrizes à esquerda e acima.
A
A
B
B
C
D
Ludwig Krippahl, 2007
B
1
0
0
0
0
C
0
2
2
1
1
E
0
1
2
3
2
D
0
1
2
2
3
0
1
2
2
4
C-D
| |
CED
53
Alinhar Sequências:
Needleman-Wunsch

Máximo, depois o máximo das submatrizes à esquerda e acima.
BC-D
A
B
C E
D
|| |
A
1
0
0
0
0
BCED
B
B
C
D
Ludwig Krippahl, 2007
0
0
0
0
2
2
1
1
1
2
3
2
1
2
2
3
1
2
2
4
54
Alinhar Sequências:
Needleman-Wunsch

Máximo, depois o máximo das submatrizes à esquerda e acima.
ABBC-D
A
B
C E
D
| || |
A
1
0
0
0
0
A-BCED
B
B
C
D
Ludwig Krippahl, 2007
0
0
0
0
2
2
1
1
1
2
3
2
1
2
2
3
1
2
2
4
55
Alinhar Sequências:
Needleman-Wunsch

Precisamos:
• Calcular os valores.
• Calcular a linha e coluna do máximo de uma
•
matriz.
Construir o alinhamento:
ABBC-D
| || |
A-BCED
Ludwig Krippahl, 2007
A
B
B
C
D
A
B
1
0
0
0
0
C
0
2
2
1
1
E
0
1
2
3
2
D
0
1
2
2
3
56
0
1
2
2
4
Alinhar Sequências:
Needleman-Wunsch
Calcular os valores:
function mat=nwcriamatriz(seq1,seq2)

Ludwig Krippahl, 2007
57
Alinhar Sequências:
Needleman-Wunsch
function mat=nwcriamatriz(seq1,seq2)
l1=length(seq1);
Cria a matriz a zeros, e
l2=length(seq2);
guarda os
mat=zeros(l1,l2);
comprimentos das
for f=1:l1
for g=1:l2
sequências.
a=(seq1(f)==seq2(g));
if (f>1) & (g>1)
m=max(max(mat(f-1,1:g-1)));
else
m=0;
endif
...
Ludwig Krippahl, 2007
58
Alinhar Sequências:
Needleman-Wunsch
...
for f=1:l1
Ciclo para percorrer
for g=1:l2
linhas e colunas
a=(seq1(f)==seq2(g));
if (f>1) & (g>1)
m=max(max(mat(1:f-1,1:g-1)));
else
m=0;
endif
mat(f,g)=a+m;
endfor
endfor
endfunction
Ludwig Krippahl, 2007
59
Alinhar Sequências:
Needleman-Wunsch
...
for f=1:l1
a é 0 ou 1 conforme os
for g=1:l2
elementos são
a=(seq1(f)==seq2(g));
diferentes ou iguais.
if (f>1) & (g>1)
m=max(max(mat(1:f-1,1:g-1)));
else
m=0;
endif
mat(f,g)=a+m;
endfor
endfor
endfunction
Ludwig Krippahl, 2007
60
Alinhar Sequências:
Needleman-Wunsch
...
for f=1:l1
for g=1:l2
a=(seq1(f)==seq2(g));
if (f>1) & (g>1)
m=max(max(mat(1:f-1,1:g-1)));
else
m=0;
endif
Se não estamos nem na
mat(f,g)=a+m;
linha 1 nem na coluna
endfor
1, m fica com o máximo
endfor
endfunction
da sub-matriz anterior.
Ludwig Krippahl, 2007
61
Alinhar Sequências:
Needleman-Wunsch
...
for f=1:l1
for g=1:l2
a=(seq1(f)==seq2(g));
if (f>1) & (g>1)
m=max(max(mat(1:f-1,1:g-1)));
else
m=0;
endif
O valor da célula f,g é o
mat(f,g)=a+m;
máximo do anterior
endfor
mais 1 se iguais
endfor
endfunction
Ludwig Krippahl, 2007
62
Alinhar Sequências:
Needleman-Wunsch
Calcular os valores:
function mat=nwcriamatriz(seq1,seq2)
 Linha e coluna do máximo da matriz:
function [l,c]=maxmatriz(t)

Ludwig Krippahl, 2007
63
Alinhar Sequências:
Needleman-Wunsch
function [l,c]=maxmatriz(t)
l=rows(t);
c=columns(t);
[ml,il]=max(t(:,columns(t)));
[mc,ic]=max(t(rows(t),:));
if ml>mc
l=il;
else
c=ic;
endif
endfunction
Ludwig Krippahl, 2007
Começar por assumir
que l e c estão na
última linha e coluna
64
Alinhar Sequências:
Needleman-Wunsch
function [l,c]=maxmatriz(t)
l=rows(t);
c=columns(t);
[ml,il]=max(t(:,columns(t)));
[mc,ic]=max(t(rows(t),:));
if ml>mc
l=il;
else
c=ic;
endif
endfunction
Ludwig Krippahl, 2007
Pelo algoritmo,
sabemos que o máximo
tem que estar ou na
última linha ou na
última coluna
65
Alinhar Sequências:
Needleman-Wunsch
function [l,c]=maxmatriz(t)
l=rows(t);
c=columns(t);
[ml,il]=max(t(:,columns(t)));
[mc,ic]=max(t(rows(t),:));
if ml>mc
l=il;
else
c=ic;
endif
endfunction
Ludwig Krippahl, 2007
ml e mc são os valores
máximo, il e ic os
indices da linha e da
coluna.
Ver help max.
66
Alinhar Sequências:
Needleman-Wunsch
function [l,c]=maxmatriz(t)
l=rows(t);
c=columns(t);
[ml,il]=max(t(:,columns(t)));
[mc,ic]=max(t(rows(t),:));
if ml>mc
l=il;
else
c=ic;
endif
endfunction
Ludwig Krippahl, 2007
Ajustamos c e l
conforme o máximo da
linha é maior que o
máximo da coluna
67
Alinhar Sequências:
Needleman-Wunsch

Construir alinhamento:
• Percorrer a matriz, e criar uma matriz com os
pares que alinham:
ABBC-D
| || |
A-BCED
Ludwig Krippahl, 2007
1,1
3,2
4,3
5,5
68
Alinhar Sequências:
Needleman-Wunsch

Construir alinhamento:
• Percorrer a matriz, e criar uma matriz com os
pares que alinham:
ABBC-D
| || |
A-BCED
1,1
3,2
4,3
5,5
• Construir o texto a partir dessa matriz.
Ludwig Krippahl, 2007
69
Alinhar Sequências:
Needleman-Wunsch


Construir o texto
ABBC-D
| || |
A-BCED
1,1
3,2
4,3
5,5
Equivale a alinhar o primeiro (A-A),e processar
o resto, subtraindo 1 aos índices do vector:
BBC-D
2,1
era 3,2
|| |
3,2
era 4,3
-BCED
4,4
era 4,4
Ludwig Krippahl, 2007
70
Alinhar Sequências:
Needleman-Wunsch

Recursividade: a função chama-se a si
mesma.
function
mat=alinhaseqs(seq1,seq2,alinhamento);
 Alinha o 1º par do vector alinhamento.
 Se há mais, chama novamente alinhaseq
com o que sobra das sequências e
alinhamento, e acrescenta à matriz.
Ludwig Krippahl, 2007
71
Alinhar Sequências:
Needleman-Wunsch
function mat=alinhaseqs(seq1,seq2,alinhamento);
p1=alinhamento(1,1);
p2=alinhamento(1,2);
s1=seq1(1:p1);
s2=seq2(1:p2);
Guardamos o primeiro
par a alinhar, p1 e p2, e
criamos s1 e s2 com
esses caracteres da
sequência
...
Ludwig Krippahl, 2007
72
Alinhar Sequências:
Needleman-Wunsch
...
sm="";
while length(s1)!=length(s2)
if length(s1)<length(s2)
s1=["-",s1]
else
s2=["-",s2]
endif
sm=[sm," "];
endwhile
sm=[sm,"|"];
mat=[s1;sm;s2];
...
Ludwig Krippahl, 2007
O sm começa vazio (é a
do meio), e enquanto
os comprimentos de s1
e s2 diferirem
acrescentamos “-” à
mais pequena e “ “ a
sm
73
Alinhar Sequências:
Needleman-Wunsch
...
sm="";
while length(s1)!=length(s2)
if length(s1)<length(s2)
s1=["-",s1]
else
s2=["-",s2]
endif
sm=[sm," "];
endwhile
sm=[sm,"|"];
mat=[s1;sm;s2];
...
Ludwig Krippahl, 2007
Acrescentamos “|” no
final de sm,
correspondendo ao
alinhamento, e criamos
a matriz com as 3
linhas.
74
Alinhar Sequências:
Needleman-Wunsch
...
if rows(alinhamento)>1
alinhamento(:,1)=alinhamento(:,1)-p1;
Se ainda há mais para alinhar
alinhamento(:,2)=alinhamento(:,2)-p2;
seq1=seq1(p1+1:length(seq1));
seq2=seq2(p2+1:length(seq2));
alinhamento=alinhamento(2:rows(alinhamento),:);
mat=[mat,alinhaseqs(seq1,seq2,alinhamento)];
endif
endfunction
Ludwig Krippahl, 2007
75
Alinhar Sequências:
Needleman-Wunsch
...
Subtraímos p1 e p2 aos índices
if rows(alinhamento)>1
alinhamento(:,1)=alinhamento(:,1)-p1;
alinhamento(:,2)=alinhamento(:,2)-p2;
seq1=seq1(p1+1:length(seq1));
seq2=seq2(p2+1:length(seq2));
alinhamento=alinhamento(2:rows(alinhamento),:);
mat=[mat,alinhaseqs(seq1,seq2,alinhamento)];
endif
endfunction
Ludwig Krippahl, 2007
76
Alinhar Sequências:
Needleman-Wunsch
...
Eliminamos os primeiros p1 e
if rows(alinhamento)>1 p2 elementos das sequências
alinhamento(:,1)=alinhamento(:,1)-p1;
(já estão alinhados)
alinhamento(:,2)=alinhamento(:,2)-p2;
seq1=seq1(p1+1:length(seq1));
seq2=seq2(p2+1:length(seq2));
alinhamento=alinhamento(2:rows(alinhamento),:);
mat=[mat,alinhaseqs(seq1,seq2,alinhamento)];
endif
endfunction
Ludwig Krippahl, 2007
77
Alinhar Sequências:
Needleman-Wunsch
...
if rows(alinhamento)>1
alinhamento(:,1)=alinhamento(:,1)-p1;
Eliminamos o primeiros par do
alinhamento(:,2)=alinhamento(:,2)-p2;
alinhamento (já está alinhado)
seq1=seq1(p1+1:length(seq1));
seq2=seq2(p2+1:length(seq2));
alinhamento=alinhamento(2:rows(alinhamento),:);
mat=[mat,alinhaseqs(seq1,seq2,alinhamento)];
endif
endfunction
Ludwig Krippahl, 2007
78
Alinhar Sequências:
Needleman-Wunsch
...
if rows(alinhamento)>1
alinhamento(:,1)=alinhamento(:,1)-p1;
E acrescentamos à matriz o
alinhamento(:,2)=alinhamento(:,2)-p2;
resultado de alinhar o resto de
seq1=seq1(p1+1:length(seq1));
acordo com o alinhamento
seq2=seq2(p2+1:length(seq2)); ajustado.
alinhamento=alinhamento(2:rows(alinhamento),:);
mat=[mat,alinhaseqs(seq1,seq2,alinhamento)];
endif
endfunction
Ludwig Krippahl, 2007
79
Alinhar Sequências:
Needleman-Wunsch

O que acontece
•
Recebe
•
Cria:
ABBCD, ABCED
1,1
3,2
4,3
5,5
A
|
A
Ludwig Krippahl, 2007
80
Alinhar Sequências:
Needleman-Wunsch

Chama novamente com
BBCD, BCED
• Cria:
BB
|
-B
Ludwig Krippahl, 2007
2,1
3,2
4,4
(posição 2)
(posição 1)
81
Alinhar Sequências:
Needleman-Wunsch

Chama novamente com
CD, CED
1,1
2,3
• Cria:
C
|
C
Ludwig Krippahl, 2007
82
Alinhar Sequências:
Needleman-Wunsch

Chama novamente com
D, ED
1,2
• Cria:
-D
|
ED
• Termina, e devolve o que criou.
Ludwig Krippahl, 2007
83
Alinhar Sequências:
Needleman-Wunsch


A chamada anterior tinha criado
C
e recebe
-D
|
|
C
ED
Devolve
C-D
| |
CED
Ludwig Krippahl, 2007
84
Alinhar Sequências:
Needleman-Wunsch


A anterior a essa tinha criado
BB
e recebe
C-D
|
| |
-B
CED
Devolve à primeira
BBC-D
|| |
-BCED
Ludwig Krippahl, 2007
85
Alinhar Sequências:
Needleman-Wunsch


A primeira tinha criado
A
e recebe
BBC-D
|
|| |
A
-BCED
Resultado final:
ABBC-D
| || |
A-BCED
Ludwig Krippahl, 2007
86
Alinhar Sequências:
Needleman-Wunsch
Percorrer a matriz, e criar uma matriz
com os pares que alinham:
ABBC-D
1,1
| || |
3,2
A-BCED
4,3
5,5
 Função principal
function
[amat,score]=nwalinha(seq1,seq2)

Ludwig Krippahl, 2007
87
Alinhar Sequências:
Needleman-Wunsch
function [amat,score]=nwalinha(seq1,seq2)
amat=nwcriamatriz(seq1,seq2);
al=[];
Cria a matriz com as
[l,c]=maxmatriz(amat);
score=amat(l,c);
pontuações e o alinhamento
while (l>1) & (c>1)
vazio
al=[l,c;al];
[l,c]=maxmatriz(amat(1:l-1,1:c-1));
endwhile
al=[l,c;al];
amat=alinhaseqs(seq1,seq2,al);
endfunction
Ludwig Krippahl, 2007
88
Alinhar Sequências:
Needleman-Wunsch
function [amat,score]=nwalinha(seq1,seq2)
amat=nwcriamatriz(seq1,seq2);
al=[];
Coordenadas do máximo. O
[l,c]=maxmatriz(amat);
score=amat(l,c);
valor nessa célula é a
while (l>1) & (c>1)
pontuação total do
al=[l,c;al];
alinhamento (número de
[l,c]=maxmatriz(amat(1:l-1,1:c-1));
elementos iguais).
endwhile
al=[l,c;al];
amat=alinhaseqs(seq1,seq2,al);
endfunction
Ludwig Krippahl, 2007
89
Alinhar Sequências:
Needleman-Wunsch
function [amat,score]=nwalinha(seq1,seq2)
amat=nwcriamatriz(seq1,seq2);
Enquanto não chega à
al=[];
primeira linha ou primeira
[l,c]=maxmatriz(amat);
coluna, vai acrescentando ao
score=amat(l,c);
while (l>1) & (c>1)
alinhamento (do fim para o
al=[l,c;al];
princípio).
[l,c]=maxmatriz(amat(1:l-1,1:c-1));
endwhile
al=[l,c;al];
amat=alinhaseqs(seq1,seq2,al);
endfunction
Ludwig Krippahl, 2007
90
Alinhar Sequências:
Needleman-Wunsch
function [amat,score]=nwalinha(seq1,seq2)
amat=nwcriamatriz(seq1,seq2);
al=[];
Acrescenta o último valor ao
[l,c]=maxmatriz(amat);
score=amat(l,c);
alinhamento (no princípio) e
while (l>1) & (c>1)
constrói a matriz.
al=[l,c;al];
[l,c]=maxmatriz(amat(1:l-1,1:c-1));
endwhile
al=[l,c;al];
amat=alinhaseqs(seq1,seq2,al);
endfunction
Ludwig Krippahl, 2007
91
Recapitulando



Estruturas e listas
•
Perceber como criar. Acrescentar, e aceder
a elementos da lista
Ficheiros: fopen, fclose, fgetl, feof.
•
Importância do identificador
Recursividade
•
Função chama-se a si própria e vai juntando
os valores. Atenção: tem que terminar.
Ludwig Krippahl, 2007
92
Dúvidas
Ludwig Krippahl, 2007
93