MO640 – Biologia Computacional
Ata de Exercícios (27/09/2004)
Autor: Roberto Hiroshi Higa - RA 876131..

1. Considere as seqüências abaixo:

s = CAGCACTTGGATTCTCGG, t = CAGCGTGG

e o sistema de pontuação que dá +1 para match, -1 para mismatch, e -2 para espaço.  Complete a tabela a seguir com as similaridades semi-globais entre s e t.

Dica: monte a matriz de programação dinâmica numa planilha de cálculo. Desta forma, com pequenas modificações nela você pode obter todos os valores acima.

Buracos em:				Similaridade semi-global
Início de s	Final de s	Início de t	Final de t
Cobra	Cobra	Cobra	Cobra	-12
Cobra	Cobra	Cobra	Não cobra	2
Cobra	Cobra	Não cobra	Cobra	-2
Cobra	Cobra	Não cobra	Não cobra	3
Cobra	Não cobra	Cobra	Cobra	-12
Cobra	Não cobra	Cobra	Não cobra	2
Cobra	Não cobra	Não cobra	Cobra	1
Cobra	Não cobra	Não cobra	Não cobra	3
Não cobra	Cobra	Cobra	Cobra	-12
Não cobra	Cobra	Cobra	Não cobra	2
Não cobra	Cobra	Não cobra	Cobra	-2
Não cobra	Cobra	Não cobra	Não cobra	3
Não cobra	Não cobra	Cobra	Cobra	-12
Não cobra	Não cobra	Cobra	Não cobra	2
Não cobra	Não cobra	Não cobra	Cobra	1
Não cobra	Não cobra	Não cobra	Não cobra	3

Solução:

Matriz de programação dinâmica para os casos: CCCC, CNCC, CCCN e CNCN

		C	A	G	C	G	T	G	G
	0	-2	-4	-6	-8	-10	-12	-14	-16
C	-2	1	-1	-3	-5	-7	-9	-11	-13
A	-4	-1	2	0	-2	-4	-6	-8	-10
G	-6	-3	0	3	1	-1	-3	-5	-7
C	-8	-5	-2	1	4	2	0	-2	-4
A	-10	-7	-4	-1	2	3	1	-1	-3
C	-12	-9	-6	-3	0	1	2	0	-2
T	-14	-11	-8	-5	-2	-1	2	1	-1
T	-16	-13	-10	-7	-4	-3	0	1	0
G	-18	-15	-12	-9	-6	-3	-2	1	2
G	-20	-17	-14	-11	-8	-5	-4	-1	2
A	-22	-19	-16	-13	-10	-7	-6	-3	0
T	-24	-21	-18	-15	-12	-9	-6	-5	-2
T	-26	-23	-20	-17	-14	-11	-8	-7	-4
C	-28	-25	-22	-19	-16	-13	-10	-9	-6
T	-30	-27	-24	-21	-18	-15	-12	-11	-8
C	-32	-29	-26	-23	-20	-17	-14	-13	-10
G	-34	-31	-28	-25	-22	-19	-16	-13	-12
G	-36	-33	-30	-27	-24	-21	-18	-15	-12

Alinhamentos para os casos CCCC e CNCC

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

C

A

G

C

-

-

-

-

G

-

-

-

-

-

T

-

G

G

Alinhamentos para os casos CCCC e CNCN

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

C

A

G

C

G

-

T

G

G

-

-

-

-

-

-

-

-

-

Matriz de programação dinâmica para os casos: CCNC, CCNN, CNNN e CNNC

		C	A	G	C	G	T	G	G
	0	-2	-4	-6	-8	-10	-12	-14	-16
C	0	1	-1	-3	-5	-7	-9	-11	-13
A	0	-1	2	0	-2	-4	-6	-8	-10
G	0	-1	0	3	1	-1	-3	-5	-7
C	0	1	-1	1	4	2	0	-2	-4
A	0	-1	2	0	2	3	1	-1	-3
C	0	1	0	1	1	1	2	0	-2
T	0	-1	0	-1	0	0	2	1	-1
T	0	-1	-2	-1	-2	-1	1	1	0
G	0	-1	-2	-1	-2	-1	-1	2	2
G	0	-1	-2	-1	-2	-1	-2	0	3
A	0	-1	0	-2	-2	-3	-2	-2	1
T	0	-1	-2	-1	-3	-3	-2	-3	-1
T	0	-1	-2	-3	-2	-4	-2	-3	-3
C	0	1	-1	-3	-2	-3	-4	-3	-4
T	0	-1	0	-2	-4	-3	-2	-4	-4
C	0	1	-1	-1	-1	-3	-4	-3	-5
G	0	-1	0	0	-2	0	-2	-3	-2
G	0	-1	-2	1	-1	-1	-1	-1	-2

Alinhamentos para o caso CCNC

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

-

-

-

-

-

-

-

-

-

C

A

G

-

C

G

T

G

G

Alinhamentos para os casos CCNN e CNNN

C

A

G

C

A

-

C

T

T

G

G

A

T

T

C

T

C

G

G

-

-

-

C

A

G

C

G

T

G

G

-

-

-

-

-

-

-

-

Alinhamentos para o caso CNNC

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

C

A

G

C

G

T

G

G

Matriz de programação dinâmica para os casos: NCCC, NNCC, NCCN e NNCN

		C	A	G	C	G	T	G	G
	0	0	0	0	0	0	0	0	0
C	-2	1	-1	-1	1	-1	-1	-1	-1
A	-4	-1	2	0	-1	0	-2	-2	-2
G	-6	-3	0	3	1	0	-1	-1	-1
C	-8	-5	-2	1	4	2	0	-2	-2
A	-10	-7	-4	-1	2	3	1	-1	-3
C	-12	-9	-6	-3	0	1	2	0	-2
T	-14	-11	-8	-5	-2	-1	2	1	-1
T	-16	-13	-10	-7	-4	-3	0	1	0
G	-18	-15	-12	-9	-6	-3	-2	1	2
G	-20	-17	-14	-11	-8	-5	-4	-1	2
A	-22	-19	-16	-13	-10	-7	-6	-3	0
T	-24	-21	-18	-15	-12	-9	-6	-5	-2
T	-26	-23	-20	-17	-14	-11	-8	-7	-4
C	-28	-25	-22	-19	-16	-13	-10	-9	-6
T	-30	-27	-24	-21	-18	-15	-12	-11	-8
C	-32	-29	-26	-23	-20	-17	-14	-13	-10
G	-34	-31	-28	-25	-22	-19	-16	-13	-12
G	-36	-33	-30	-27	-24	-21	-18	-15	-12

Alinhamentos para os casos NCCC e NNCC

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

C

A

G

C

-

-

-

-

G

-

-

-

T

-

-

-

G

G

Alinhamentos para os casos NCCN e NNCN

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

C

A

G

C

G

-

T

-

G

G

-

-

-

-

-

-

-

-

Matriz de programação dinâmica para os casos: NCNC, NCNN, NNNN e NNNC

		C	A	G	C	G	T	G	G
	0	0	0	0	0	0	0	0	0
C	0	1	-1	-1	1	-1	-1	-1	-1
A	0	-1	2	0	-1	0	-2	-2	-2
G	0	-1	0	3	1	0	-1	-1	-1
C	0	1	-1	1	4	2	0	-2	-2
A	0	-1	2	0	2	3	1	-1	-3
C	0	1	0	1	1	1	2	0	-2
T	0	-1	0	-1	0	0	2	1	-1
T	0	-1	-2	-1	-2	-1	1	1	0
G	0	-1	-2	-1	-2	-1	-1	2	2
G	0	-1	-2	-1	-2	-1	-2	0	3
A	0	-1	0	-2	-2	-3	-2	-2	1
T	0	-1	-2	-1	-3	-3	-2	-3	-1
T	0	-1	-2	-3	-2	-4	-2	-3	-3
C	0	1	-1	-3	-2	-3	-4	-3	-4
T	0	-1	0	-2	-4	-3	-2	-4	-4
C	0	1	-1	-1	-1	-3	-4	-3	-5
G	0	-1	0	0	-2	0	-2	-3	-2
G	0	-1	-2	1	-1	-1	-1	-1	-2

Alinhamentos para o caso NCNC

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

-

-

-

-

-

-

-

-

-

C

A

G

-

C

G

T

G

G

Alinhamentos para os casos NCNN e NNNN

C

A

G

C

A

-

C

T

T

G

G

A

T

T

C

T

C

G

G

-

-

-

C

A

G

C

G

G

G

G

-

-

-

-

-

-

-

-

Alinhamentos para o caso NNNC

C

A

G

C

A

C

T

T

G

G

A

T

T

C

T

C

G

G

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

C

A

G

C

G

T

G

G