View
53
Download
4
Category
Preview:
DESCRIPTION
Class, Markov
Citation preview
MODELOS DE MARKOVDilvan Moreira (Baseado em material do prof. André Carvalho)
Leitura
Introduction to Computational Genomics: A Case Studies Approach Capítulo 4
18/04/23André de Carvalho - ICMC/USP
3
Tópicos
Introdução Receptores de odor Cadeias de Markov Escondidas Aplicações em Bioinformática Estudo de caso Algoritmos
18/04/23André de Carvalho - ICMC/USP
4
Introdução
Em 2004, Richard Axel and Linda Buck receberam o prêmio Nobel Elucidação do sistema olfativo Inclui uma grande família de proteínas
Receptores de odor (OR) Odorantes ou olfativos Combinação permite sentir mais de 10.000 odores diferentes Localizados na superfície de células da passagem nasal Detectam moléculas de odores quando são inaladas e passam
informação para o cérebro
18/04/23André de Carvalho - ICMC/USP
5
Receptores Olfativos
Devem ser capaz de atravessar membrana celular para levar informação ao cérebro
Contém 7 domínios transmembranas Trechos de AAs altamente hidrofóbicos que
interagem com a gordura da membrana Proteína tem trechos alternados de AAs hidrofóbicos
e hidrofílicos Descoberta permitiu descrição de
receptores similares Detecção de sabor e de feromônio
18/04/23André de Carvalho - ICMC/USP
6
Receptores Olfativos
Maior família de genes do genoma humano 1000 genes, 40% deles funcionais
600 são chamados de pseudogenes Genes funcionais inativos ou com defeito Resultado da seleção natural
Predominância de outro sentido (visão) Geralmente semelhantes aos genes
funcionais Cachorros (1500 genes) e ratos (1000
genes) têm 80% de seus genes funcionais
18/04/23André de Carvalho - ICMC/USP
7
Receptores Olfativos
Análise de OR requer ferramentas computacionais mais sofisticadas Similaridade entre vários genes ORs é
baixa para detectar com alinhamento de pares Sinais importantes podem ser detectados
com alinhamento múltiplo de todos os ORs Genoma tem muito ruído
Ex.: regiões com elevada quantidade de GC podem ter trechos longos de As e Ts
18/04/23André de Carvalho - ICMC/USP
8
Modelagem de Seqüências
Modelos Multinomiais Nucleotídeos são independentes e
identicamente distribuídos p = (pA, pC, pG, pT)
Modelos de Markov Probabilidade de um símbolo depende dos
símbolos anteriores
18/04/23André de Carvalho - ICMC/USP
9
Cadeias de Markov Ocultas
Modelos multinomiais e de Markov Não conseguem capturar isoladamente
muitas das propriedades de seqüências Cadeias de Markov ocultas (HMM)
Hidden Markov Models Um dos principais algoritmos da
Bioinformática Combinam modelos de sequências
multinomiais e de Markov
18/04/23André de Carvalho - ICMC/USP
10
Cadeias de Markov Ocultas
Muito usadas para reconhecimento de voz Utilizadas em 1989 para segmentação de
sequências de DNA Churchill segmentou sequências de DNA em
regiões com usos similares de nucleotídeos Posteriormente usado para outras aplicações:
Identificação (reconhecimento) de genes Predição da estrutura de proteínas
Permite identificar padrões que não têm uma estrutura rigidamente definida
18/04/23André de Carvalho - ICMC/USP
11
Cadeias de Markov Ocultas
Modela uma seq. como sendo indiretamente gerada por uma cadeia de Markov Cada posição na sequência tem um estado
oculto A sequência é modelada como um
processo duplamente aleatório Gerar a HMM Transformar a cadeia oculta na sequência
observada Usando uma distribuição multinomial diferente para
cada estado da cadeia de Markov
18/04/23André de Carvalho - ICMC/USP
12
Cadeias de Markov Ocultas
Autômatos finitos Conjunto de N estados, H (alfabeto oculto) Um alfabeto de M símbolos observáveis, S Probabilidades de transição entre os
estados, T Probabilidades de emissão dos símbolos em
cada estado, E
18/04/23André de Carvalho - ICMC/USP
13
Cadeias de Markov Ocultas
Idéias centrais: Uma cadeia de caracteres é representada
por um sistema Um sistema pode ter estados distintos Um sistema pode mudar entre estados com
probabilidade de transição T Em cada estado, o sistema emite símbolos
para uma cadeia com probabilidade de emissão E
18/04/23André de Carvalho - ICMC/USP
14
Modelos Ocultos de Markov
Parâmetros do modelo: Probabilidades de
transição: definem as probabilidades com as quais a cadeia de Markov muda de estado
18/04/23André de Carvalho -
ICMC/USP15
Modelos Ocultos de Markov
Parâmetros do modelo: Probabilidades de
transição: definem as probabilidades com as quais a cadeia de Markov muda de estado
Matriz de Transição
h1 h2 ... hN
h1a d g
h2b e h
...
hNc f i
)|(),( 1 khlhPlkT ii
18/04/23André de Carvalho -
ICMC/USP16
Modelos Ocultos de Markov
Parâmetros do modelo: Probabilidades de
transição: definem as probabilidades com as quais a cadeia de Markov muda de estado
Probabilidades de emissão: probabilidades com as quais os símbolos da seqüência observável são produzidos em cada um dos estados
18/04/23André de Carvalho -
ICMC/USP17
Modelos Ocultos de Markov
Parâmetros do modelo: Probabilidades de
transição: definem as probabilidades com as quais a cadeia de Markov muda de estado
Probabilidades de emissão: probabilidades com as quais os símbolos da seqüência observável são produzidos em cada um dos estados
Matriz de Emissão
s1 s2 ... sM
h1a d g
h2b e h
...
hNc f i
)|(),( khbsPbkE ii
18/04/23André de Carvalho - ICMC/USP
18
Modelos Ocultos de Markov
h: seqüência de estados ocultos s: seqüência de símbolos Probabilidade inicial para os estados:
As probabilidades dos símbolos em cada estado e das transições entre estados devem somar 1.
)(),0( 1 khPkT
18/04/23André de Carvalho - ICMC/USP
19
Modelos Ocultos de Markov
Os parâmetros do modelo podem ser estimados usando o algoritmo Expectation-Maximization (EM), com base em dados conhecidos
18/04/23André de Carvalho - ICMC/USP
20
Exemplo
Dois dados: um justo e outro viciado Dada uma sequência de lançamentos, é
possível adivinhar qual dos dados originou cada valor da sequência?
18/04/23André de Carvalho - ICMC/USP
21
Exemplo
Justo
h1
1: 0.16672: 0.16673: 0.16674: 0.16675: 0.16676: 0.1667
0.9Viciado
h2
0.90.1
0.1
1: 0.10002: 0.10003: 0.10004: 0.10005: 0.10006: 0.5000
oculta: h = 1111111111111111111122221111111222222222
visível: s= 4553653163363555133362665132141636651666
Maior freqüência de 6
18/04/23André de Carvalho - ICMC/USP
22
Modelos Ocultos de Markov
Probabilidade de uma sequência oculta h:
Probabilidade de gerar uma sequência de símbolos s dada uma sequência de estados ocultos h:
n
iii
n
iii hhThThhPhPP
211
211 ),(),0()()()(h
n
iii
n
iii shEhsPP
11
),()|()|( hs
18/04/23André de Carvalho - ICMC/USP
23
Modelos Ocultos de Markov
Se h é conhecida (raro), probabilidade conjunta de s e h:
)()|(),( hhshs PPP
18/04/23André de Carvalho - ICMC/USP
24
Modelos Ocultos de Markov
Se h é desconhecida (frequente), pode-se usar o teorema da probabilidade total para calcular a probabilidade de s:
n
jn
j
jjj PPPPHH hh
hhshss )()|(),()(
Todas as cadeias ocultas de tamanho n
Cresce exponencialmente com n
18/04/23André de Carvalho - ICMC/USP
25
Modelos Ocultos de Markov
Sequência mais provável
),(maxarg* hshh
PnH
Determinada com o algoritmo Viterbi
(programação dinâmica)
18/04/23André de Carvalho - ICMC/USP
26
HMM – Aplicações em Bioinformática Gary Churchill foi o primeiro a usar HMM em genômica,
em 1989 Segmentação de seqüências de DNA em regiões de uso similar
dos nucleotídeos
Hoje: Segmentação Alinhamentos múltiplos Predição da função de proteínas Descoberta de genes
18/04/23André de Carvalho - ICMC/USP
27
Segmentação
Tarefa mais comum As seqüências (genes ou proteínas)
podem conter regiões com propriedades distintas
Inferir os estados escondidos que representam essas regiões, bem como determinar seus limites na seqüência para: melhor anotação entender melhor a dinâmica da seqüência
18/04/23André de Carvalho - ICMC/USP
28
Segmentação - exemplo
Genoma do bacteriófago lambda Tem longos trechos da seqüência que
são: ricos em GC ricos em AT
HMM para segmentar o genoma em regiões com essas características
18/04/23André de Carvalho - ICMC/USP
29
Segmentação - exemplo
Estados ocultos: “rico em GC” e “rico em AT”
Símbolos observáveis: A, C, G e T Estima os parâmetros:
Algoritmo EM Matrizes de transição e emissão iniciais
aleatórias Assumindo 2 estados ocultos e 4 símbolos
visíveis
18/04/23André de Carvalho - ICMC/USP
30
Segmentação - exemplo
Rico em GC
A: 0.2462C: 0.2476G: 0.2985T: 0.2077
0.9998
Rico em AT
0.0002
A: 0.2700C: 0.2084G: 0.1981T: 0.3236
0.9998
0.0002
18/04/23André de Carvalho - ICMC/USP
31
Segmentação - exemplo
Rico em GC
A: 0.2462C: 0.2476G: 0.2985T: 0.2077
0.9998
Rico em AT
0.0002
A: 0.2700C: 0.2084G: 0.1981T: 0.3236
0.9998
0.0002
Transições são raras
Maior probabilidadede gerar G e C
Maior probabilidadede gerar A e T
18/04/23André de Carvalho - ICMC/USP
32
Segmentação - exemplo
Usando o algoritmo Viterbi e o modelo estimado, obtém-se a segmentação da sequência nos pontos mostrados:
18/04/23André de Carvalho - ICMC/USP
33
Alinhamentos múltiplosPredição da função de proteínas
Usa profile HMM (pHMM) pHMMs podem ser vistos como:
Descrições abstratas de uma família de proteínas
Resumos estatísticos de um alinhamento múltiplo
18/04/23André de Carvalho - ICMC/USP
34
Profile HMM
Codifica informações sobre a frequência dos resíduos e também das inserções e deleções em cada coluna do alinhamento múltiplo
Criado a partir do alinhamento múltiplo de sequências homólogas
Para cada coluna no alinhamento, o modelo tem: Estado de equiparação (match) – distribuição dos resíduos Estado de inserção Estado de deleção
Cada estado de equiparação e inserção tem uma Matriz de Emissões com as probabilidades de emissão de cada resíduo (aminoácidos ou nucleotídeos)
Resíduos não são emitidos nos estados de deleção
18/04/23André de Carvalho - ICMC/USP
35
Exemplo
V I V A L/D A S/L V/L E/I Sb e
i G/Aiii i i i i ii
d d d d d d - d - d
VIVALASVEGAS
VIVADA-VI--S
VIVADALL--AS
Estados em que símbolos são emitidos
Estados em que símbolos extras são emitidos
Estados em que gaps são emitidos (deleção)
Transições com alta probabilidadeTransições com baixa probabilidade
Cada caminho representa uma possível sequência
18/04/23André de Carvalho - ICMC/USP
36
Exemplo
pHMM permite calcular o grau com que uma seqüência se ajusta ao modelo: Para cada sequência que passa pelo modelo,
pode ser atribuída uma probabilidade ou pontuação
Pontuação alta significa ajuste ao modelo Usado para procurar em uma base de
dados por outros membros da família de proteína: Existem repositórios de pHMMs de muitas
famílias de proteínas: Pfam
18/04/23André de Carvalho - ICMC/USP
37
Exemplo
Como é feito? Usa Blast para separar uma base de dados de proteínas em
famílias de proteínas relacionadas Constrói um alinhamento múltiplo para cada família Constrói um profile HMM e otimiza seus parâmetros para cada
um dos alinhamentos múltiplos Alinha a seqüência alvo com cada um dos pHMM para
encontrar o melhor ajuste entre a seqüência alvo e um dos pHMM
A família da sequência alvo é aquela usada no pHMM com melhor ajuste (maior probabilidade)
Algoritmo de Viterbi: calcula o melhor caminho através do modelo
Algoritmo Forward: calcula a soma das probabilidades de todos os alinhamentos possíveis
18/04/23André de Carvalho - ICMC/USP
38
Descoberta de genes
HMM permite integrar vários sinais diferentes, que são de natureza probabilística, na busca de genes Sítios de ligação de fatores de transcrição ORFs Sítios de splice Códons de início e parada
Com o modelo construído, usa-se o algoritmo de Viterbi para encontrar os genes (sequência de nucleotídeos que compõem o gene)
18/04/23André de Carvalho - ICMC/USP
39
Estudo de caso
Receptores olfativos (OR) Pertencem à família de proteínas “receptores
7-TM” Para perceber as moléculas fora da célula e
sinalizar sua descoberta dentro da célula os OR precisam atravessar a membrana da célula
Para isso, OR tem 7 trechos com aminoácidos altamente hidrofóbicos alternando com regiões hidrofílicas, que caracterizam a função dessas proteínas
18/04/23André de Carvalho - ICMC/USP
40
Estudo de caso
Como identificar se uma proteína X pertence a uma determinada família conhecida? Comparação de pares de seqüências não é
suficiente para identificar os membros da família dos “receptores 7-TM”
O alinhamento com o pHMM da família é mais adequado
18/04/23André de Carvalho - ICMC/USP
41
Estudo de caso
Comparação da proteína X Com uma seqüência típica da família
“receptores 7-TM” usando alinhamento global Score: 54.8
Com o pHMM construído usando milhares de seqüências alinhadas Score: 154.6
O sinal indicando que a proteína pertence à família “receptores 7-TM” é muito mais forte usando o pHMM
18/04/23André de Carvalho - ICMC/USP
42
Estudo de caso
Segmentando os OR em regiões hidrofóbicas e hidrofílicas
HMM com 2 estados: “dentro da membrana” e “fora da membrana”
18/04/23André de Carvalho - ICMC/USP
43
Estudo de caso
Dentro
A: 15R: 11...V: 31
p1
Fora
p2
A: 15R: 11...V: 31
p4
p3
Com os valores conhecidos ou estimados pelo EM, aplica o algoritmo Viterbi para segmentar a proteína nas regiões de interesse
18/04/23André de Carvalho - ICMC/USP
44
Estudo de caso
18/04/23André de Carvalho - ICMC/USP
45
Algoritmo Viterbi
Dada uma sequência s de tamanho n e um HMM com parâmetros T e E, acha a sequência escondida mais provável
Cria uma tabela V de tamanho |H|x(n+1);
Inicializa i = 0; V(0,0) = 1; V(k,0) = 0 para k > 0;
Para i = 1:n, calcula cada entrada usando a relação
recursiva
V(j,i) = E(j,s(i)) * maxk {V(k, i-1) * T(k, j) }
pointer(i, j) = arg maxk {V(k, i-1)*T(k, j) }
Saída: P(s,h*) = maxk {V(k,n)}
Trace-back: i = n:1, using: h*i-1 = pointer(i, h*i)
Saída: h*(n) = arg maxk {V(k,n)}
18/04/23André de Carvalho - ICMC/USP
46
Algoritmo Forward
Dada uma sequência s de tamanho n e um HMM com parâmetros T e E, calcula a probabilidade de uma sequência
Cria uma tabela F de tamanho |H|x(n+1);
Inicializa i = 0; F(0, 0) = 1; F(k, 0) = 0 para k > 0;
Para i = 1:n, calcula cada entrada usando a relação
recursiva
F(j,i) = E(j,s(i)) * ∑k {F(k, i-1) * T(k, j) }
Saída: P(s) = ∑k F(k, n)
18/04/23André de Carvalho - ICMC/USP
47
Algoritmo EMExpectation Maximization
Dada uma sequência s de tamanho n e um HMM com parâmetros T e E desconhecidos, estima os parâmetros
1. Inicializa h, E and T;
2. Dado s e h, estima E e T apenas contando os símbolos;
3. Dado s, E e T, estima h com o algoritmo de Viterbi, p. ex;
4. Repete os passos 2 e 3 até que algum critério de parada
seja satisfeito
18/04/23André de Carvalho - ICMC/USP
48
Conclusão
Importância do alinhamento de seqüências
Perguntas?
Recommended