Bioinformática 55



Baixar 24.65 Kb.
Encontro14.05.2018
Tamanho24.65 Kb.

Bioinformática 55

LEBM/IST

2005/2006

Laboratório 4: Modelos probabilísticos

O objectivo deste trabalho é analisar a utilidade das HMMs na modelação de problemas reais. O problema considerado é um problema simples, conhecido por “Fair Bet Casino”.




  1. Considere a seguinte situação. Um agente responsável por um jogo num casino tem duas moedas, possivelmente viciadas. O agente começa o jogo sempre com a moeda m1 e em cada jogada muda de moeda, podendo escolher a mesma moeda ou a outra com uma determinada probabilidade. O jogador apenas observa o resultado da jogada, isto é, só vê cara ou coroa, sem nunca saber qual das moedas está a ser utilizada.

Este problema pode ser modelado pela seguinte HMM:

q1

1-q2

1-q1








Coroa:

(1-p2)



Cara: p1

q2

Cara: p2


Coroa:

(1-p1)


Existem dois estados, S1 e S2, que correspondem a cada uma das moedas, e é possível fazer duas observações cara ou coroa. O sistema pode ter início, com igual probabilidade, em qualquer um dos estados. Os restantes parâmetros correspondem a: p1 é a probabilidade de ver cara no estado S1; p2 é a probabilidade de ver cara no estado S2; q1 é a probabilidade de transição do estado S1 para o estado S2 e q2 é a probabilidade de transição do estado S2 para o estado S1.


    1. Admita que no estado S1 apenas é possível observar cara e que no estado S2 apenas é possível observar coroa. A probabilidade de transição entre estados (ou ficar no mesmo) é 0.5. Desenhe uma HMM que descreva esta situação, escrevendo os valores para os vários parâmetros.

    2. Para uma determinada sequência de caras e coroas de tamanho T (X1,T), quantos caminhos existem na HMM da alínea anterior capazes de gerar a sequência X1,T com probabilidade diferente de zero?

    3. Qual é a probabilidade de observar a sequência X1,T de acordo com a HMM da alínea a.? Calcule o valor P(X1,T).

    4. Agora considere que os estados S1 e S2 correspondem a uma moeda viciada e não viciada, respectivamente. As probabilidades de ver cara e coroa são idênticas para o estado S1 e igual a 0.6 e 0.4 para o estado S2. É possível transitar entre estados com uma probabilidade q=0.3. Desenhe esta HMM calculando os respectivos parâmetros.

    5. Considere {Cara, Coroa}={1,0} e a seguinte sequência X={1,1,0,0,0}. Determine a sequência de estados mais provável para a obtenção da sequência X, considerando a HMM da alínea d.



  1. Considere o problema da identificação de ilhas CpG numa longa sequência de DNA. As tabelas seguintes ilustram as probabilidades de transição de dois modelos de Markov, um para as ilhas CpG (modelo +) e outro para as restantes sequências (modelo -). Estes modelos foram obtidos a partir de um conjunto de sequências de DNA humano onde foram identificadas 48 ilhas CpG.


Modelo +

+

A

C

G

T

A

0.180

0.274

0.426

0.120

C

0.171

0.368

0.274

0.188

G

0.161

0.339

0.375

0.125

T

0.079

0.355

0.384

0.182



Modelo -

-

A

C

G

T

A

0.300

0.205

0.285

0.210

C

0.322

0.298

0.078

0.302

G

0.248

0.246

0.298

0.208

T

0.177

0.239

0.292

0.292

Nestas tabelas cada linha representa a probabilidade de um nucleótido ser seguido por cada uma das 4 bases. A soma das probabilidades em cada linha é igual a 1.




  1. Se a probabilidade de estar numa ilha CpG for igual à probabilidade de estar fora, escreva a matriz com as probabilidades de transição para uma HMM que represente de uma forma unificada os modelos de Markov + e – apresentados nas tabelas anteriores.

  2. Considerando a matriz de transição de estados obtida e uma matriz de emissão onde cada estado emite apenas um símbolo (o estado Y+ e Y- emitem apenas o símbolo Y), calcule a probabilidade da sequência CGCG ser obtida a partir da sequência de estados (C+,G-,C-,G+).

  3. Utilizando o algoritmo de Viterbi, a HMM da alínea anterior e a sequência CGCG, calcule qual o caminho mais provável nesta HMM que leve à geração desta sequência.





©aneste.org 2017
enviar mensagem

    Página principal