Aula5.Modelos de Markov

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


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


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


6


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


7


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


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


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


10


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


11


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


12


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


13


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


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




Matriz de Transição

h1 h2 ... hN

h1a d g

h2b e h

...

hNc f i

)|(),( 1 khlhPlkT ii


ICMC/USP16




Probabilidades de emissão: probabilidades com as quais os símbolos da seqüência observável são produzidos em cada um dos estados


ICMC/USP17




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


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


19


Os parâmetros do modelo podem ser estimados usando o algoritmo Expectation-Maximization (EM), com base em dados conhecidos


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?


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


22


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


23


Se h é conhecida (raro), probabilidade conjunta de s e h:

)()|(),( hhshs PPP


24


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


25


Sequência mais provável

),(maxarg* hshh

PnH

Determinada com o algoritmo Viterbi

(programação dinâmica)


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


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


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


29


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


30


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


31


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


32


Usando o algoritmo Viterbi e o modelo estimado, obtém-se a segmentação da sequência nos pontos mostrados:


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


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


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


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


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


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)


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


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


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


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”


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


44

Estudo de caso


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)}


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)


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


48

Conclusão

Importância do alinhamento de seqüências

Perguntas?

Documents

Aula5.Modelos de Markov