Embed Size (px)
Citation preview
1
3/17/2005 1
Ana Teresa FreitasAna Teresa Freitas
INESCINESC--ID/ISTID/IST
Algor itmos paraAlgor itmos para a a DetecDetecççãoão de de PromPromotores otores em Sequênciasem Sequências de DNAde DNA
3/17/2005 2
Como analisar todosestes dados?
2
3/17/2005 3
Gene de um organismo Eukar iota
Região promotoraTSS
5’ 3’
UTR UTR
CodãoATG
CodãoSTOPExões
Intrões
Transcr ição
Splicing
Tradução
Pré-mRNA
mRNA
Proteína
5’ Cap 3’ poly-A
3/17/2005 4
Transcr ição
The CellG. Cooper
3
3/17/2005 5
Sequência DNA
genejunk DNA
geneUTR-5' UTR-3'
exãointrão
TSS
TFBSTFBS
TATA boxINR DSE
e1 e2 e5e4e3
Distal Promoter Proximal promoter Core promoter
INR DSE
3/17/2005 6
Descobr ir uma estrutura para a regiãopromotora: qual éo desafio?
�Não existe apenas um tipo de promotor�São necessários elementos regulatórios adicionais�A transcrição pode ser activada ou reprimida por proteínas
reguladoras�Nem todos os factores regulatórios estão caracterizados
ACCGATTATCA
Consenso (TFBS)
�Pequenas sequências (12 a 20 nucleótidos)
Factor de Transcrição (TF)
4
3/17/2005 7
Pr incipais Acontecimentos no Início da Transcr ição
� A RNA polymerase II e um conjunto de Factores de Transcrição (TFs) genéricos são recrutados para a região promotora e para a posição de início da transcrição (TSS)
Consensos
TATA box
Região Início (INR)
TSSDNA
RNA Poly I I
TFI IDTBP
Proximal PromoterProximal Promoter Core PromoterCore Promoter
TFIIETFIIH
3/17/2005 8
RNA Poly I I
TFIIETFIIH
TFI IDTBP
INR
TSS
TATA
corepromoter DNA
� A proteina TBF provoca uma dobra de 90º na região promotora
� TATA box: -20 to -30; ConsensoTATAWAW (W= A or T)
� CCAAT box: -50 TO -130; Consenso GGYCAATCT
5
3/17/2005 9
TFIID
RNA Poly I I
TFIIA
INR
TSS
TATA
corepromoter
TFIIETFIIH
Distal promoter / enhancer
Proximalpromoter
TF1
TF2
TF3 TF4
TF5
DNA looping
TFIIB
TBP
TFIIB
DNA
� Factores de Transcrição acessórios: conjunto de proteinas activadoras ou repressoras da transcrição
3/17/2005 10
Sequências de consenso para vár ios factores de transcição
6
3/17/2005 11
Algor itmos�Procurar sequências de consenso/promotores em
genomas éuma tarefa verdadeiramente difícil
�Os algoritmos existentes procuram nos genomas sequências pré-definidas ou tentam extrair consensos comuns a um conjunto de sequências
�Estão normalmente limitados tanto no número como no tamanho das sequências a tratar
�Os modelos utilizados para reconhecer a região promotora ainda não são satisfatórios
3/17/2005 12
Algor itmos exactos
�Algoritmo de alinhamento� Algoritmo de programação dinâmica
�Algoritmo para emparelhamento de cadeias de caracteres� Utiliza estruturasde dados sofisticadas: árvoresde
sufixos.
7
3/17/2005 13
Alinhamento de sequências
�Exemplo:CGCTATATTATACTA
CGCTATAT--
---TATACTA
--CGCTATAT
TATACTA---
igual(match)
diferente(mismatch)
espaçamento(gap)
• Qual éo melhor?
• Qual tem mais significado biológico?
3/17/2005 14
Exemplo:
� ���������� �
� ������� �0 + 0 + (-1) + (-1) + 2 + 2 + 2 + 0 + 0 + 0 = 4
0 + 0 + 0 + 2 + 2 + 2 + 2 + (-1) + 0 + 0 = 7
CGCTATAT--
---TATACTA
--CGCTATAT
TATACTA---
����������������� ������ � � ������ ���� ��
��� �������������������� �����
G
T
C
A
GTCA
2-1-1-1
-12-1-1
-1-12-1
-1-1-12
8
3/17/2005 15
Algor itmos de alinhamento
�Considereduas sequências de tamanho n
�Existem
possíveis alinhamentos globais.
�Queremos encontrar o melhor de todos.
nn
n
n
n n
π
2
2
2
)!(
)!2(2≈=��
�
����
�
3/17/2005 16
Qual a dificuldade?
�Para n = 20, temoscercade 120 biliões de possíveis alinhamentos
�Pretendemos alinharsequências muitomaiores• Algumas proteinas têm
1000 aminoácidos
• Os genes podem ter vários milhares de pares de bases
9
3/17/2005 17
Programação dinâmica : é um algor itmoque permiteobter alinhamentos óptimosutilizando uma função de mér ito
�Os algoritmos mais simples são conhecidos por“pairwisesequence alignment algorithms”
�Problema: PairSequenceAlignment�Entrada: Duas sequências X,Y
Matriz de mérito s(x,y)
Valor do espaçamento d
�Saída: O melhor alinhamento das sequências
3/17/2005 18
Programação Dinâmica
Sequência Y
Sequência XMelhor alinhamento anter ior
Novo melhor alinhamento = melhor anter ior + melhor local
... ... ... ...
10
3/17/2005 19
Alinhamento Global: Needleman-Wunsh (1970)
�Ideia: Obter um alinhamento óptimo utilizando as melhores soluções obtidas anteriormenteno alinhamento de sub-sequências.
T
A
C
A
XT
A
T
TATATCGC
xi
Matr iz F
yj
3/17/2005 20
F(i,j)F(i-1,j)
F(i,j-1)F(i-1,j-1)
s(xi,yj)
-d
-d
��
�
−−−−
+−−=
djiF
djiF
yxsjiF
jiFji
)1,(
),1(
),()1,1(
max),(
Calcular o melhor F(i,j )
• xi alinha com yj
• xi alinha com espaço• yj alinha com espaço
�Condição inicial: F(0,0) = 0, F(i,0) = -id, F(0,j)=-jd
� Guardar o caminho atéao valor calculado
11
3/17/2005 21
Exemplo:
0T
0A
0C
0A
0T
0A
0T
000000000
TATATCGC
2-1-1-1G
-12-1-1T
-1-12-1C
-1-1-12A
GTCAs(xi,yj)
d = 0
F(n,m) éo valordo melhoralinhamento
0 0 2 2 2 2
0 0 0 2 4 4 4 4
0 0 0 2 4 6 6 6
0 0 0 2 4 6 8 8
2 2 2 2 4 6 8 8
2 2 2 4 4 6 8 10
2 2 2 4 6 6 8 10
��
�
−=−−−=−−
−=+−−=
00)1,(
00),1(
10),()1,1(
max),(
djiF
djiF
yxsjiF
jiFji
0 2
��
�
−=−−−=−−
+=+−−=
00)1,(
00),1(
20),()1,1(
max),(
djiF
djiF
yxsjiF
jiFji
3/17/2005 22
• Diagonal- xi alinhacom yj
• Cima– yi alinhacom espaço• Esquerda– xj alinhacom espaço
0T
0A
0C
0A
0T
0A
0T
000000000
TATATCGC
0 0 0 2 2 2 2 2
0 0 0 2 4 4 4 4
0 0 0 2 4 6 6 6
0 0 0 2 4 6 8 8
2 2 2 2 4 6 8 8
2 2 2 4 4 6 8 10
2 2 2 4 6 6 8 10
--AA
TTTT
CGCTATACGCTATA--------TATACTATAC
Função de mérito: 0 + 0 + 0 + 2 + 2 + 2 + 2 + 0 + 2 + 0 = 10
i
j
12
3/17/2005 23
Análiseda complexidade
�Espaço: (n+1) x (m+1) números
�Operações por número : 3 somas e um max
�Complexidade O(nm) em tempo e memória• Podeser utilizado em sequências de tamanho
moderado, mas não no alinhamento de genomas
• Sequências com n =10 ( 10-9 segundos )
• Sequências com n = 1 000 000 000 ( 3 anos )– Para um tempo de execução linear com n ( 0,1 segundos )
3/17/2005 24
Algor itmo para Emparelhamento de Cadeias de Caracteres
�Identifica todas as sub-sequências comuns a um conjunto de sequências
�Constrói em tempo linear uma árvore de sufixos (Ukkonen’s method)
�Procura na árvore os modelos especificados para os promotores
�O significado biológico dos modelos encontrados éobtido por análise dos resultados
13
3/17/2005 25
CGCTATATCGCTATAT
TATACTATATACTA
S1:
S2:
CC
GGCC
TT
TT
TTAA
AA
$1$1
GG
CC
TT
AA
TT
AA
TT
$1$1
$1$1
TT
TT
TT
AA
AA
AA
$1$1
TTAA
TT$1$1$1$1
Construção da árvorede sufixos
$1$1
CC
TT
AA
$2$2
CC
TT
AA
$2$2
CC
TT
AA
$2$2
$2$2
$2$2
CC TT AA $2$2
$2$2
TT
AA
TT
TT
$1$1
AA
[1,2]
[1]
[1,2]
[1,2]
[1]
[1]
[1]
[1]
[1]
[1]
[1]
[1]
[1][2]
[1]
[1]
[1]
[1]
[1]
[1]
[1]
[2]
[2]
[2]
[2]
[2]
[1]
[1,2]
[1,2]
[1]
[2] [2][2]
[2]
[2]
[2]
[1,2]
[1,2] [1,2]
[1,2]
[1,2]
$2$2
$1$1
3/17/2005 26
CC
GGCC
TT
TT
TTAA
AA
$1$1
GG
CC
TT
AA
TT
AA
TT
$1$1
$1$1
TT
TT
TT
AA
AA
AA
$1$1
TTAA
TT$1$1$1$1
$1$1
CC
TT
AA
$2$2
CC
TT
AA
$2$2
CC
TT
AA
$2$2
$2$2
$2$2
CC TT AA $2$2
$2$2
TT
AA
TT
TT
$1$1
AA
[1,2]
[1]
[1,2]
[1,2]
[1]
[1]
[1]
[1]
[1]
[1]
[1]
[1]
[1][2]
[1]
[1]
[1]
[1]
[1]
[1]
[1]
[2]
[2]
[2]
[2]
[2]
[1]
[1,2]
[1,2]
[1]
[2] [2][2]
[2]
[2]
[2]
[1,2]
[1,2] [1,2]
[1,2]
[1,2]
Procura de modelos de tamanho 3 ou +
CC TT AA
TT AA TT AAAA TT AA
CGCTATATCGCTATAT
TATACTATATACTA
TT AA TT
14
3/17/2005 27
3/17/2005 28
