Catene di Markov

Processo di Markov

lo stato successivo dipende solo dallo stato presente

condizionati al presente, il passato ed il futuro sono indipendenti

ogni distribuzione congiunta può essere fattorizzata in distribuzioni condizionali

transizioni di stato

matrici

diagrammi

q ij= p(x t+1=i | xt=j)

HMM
(hidden markov models)

hidden states and observed process

quello che vedo viene emesso da stati che non posso osservare

ogni stato determina solo lo stato successivo ed è influenzato solo dallo stato precedente

stati derivano da

  • analisi fenomeno
  • scoperto dai dati di train

ciascuno stato ha una determinata probabilità di emettere simboli o di effettuare una transizione

in biologia

  • predizione geni
  • modellazione sequenze di proteine
  • allineamento sequenze di proteine
  • ricerca database di proteine
  • predizione struttura proteine
  • ...

Family profiling

creo dataset di training dove raggruppo sequenze proteiche 'omologhe'

addestro il modello di Markov, per usarlo per identificare nuovi membri della famiglia

costruzione HMM

MATCH

DELETE

INSERT

la posizione viene mantenuta con o senza mutazioni

la posizione è cancellata

ammino acidi inseriti tra due posizioni

how many states? 3M + 3
how many transition? 9M+3
how many emissions? 40M+20

inizializzazione HMM

come decidere lunghezza modello?

una volta utilizzavano allineamenti multipli

assegno un match state ad ogni colonna con gaps minore del 50%

uso un range di lunghezza modello. Se la probabilità di transizione da un match state ad un delete state è maggiore di 0,5, elimino M i+1

se in una colonna ho una frazione rilevante di gap, posso modellare quella colonna come inserzione tra due colonne

oppure decido automaticamente che sia un match state

inizializzazione parametri

inizializzazione uniforme delle probabilità di transizione è ok in molti casi

inizializzazione di probabilità di emissione di stati di inserzione è ok in molty casi

per inizializzare la probabilità di emissione di un match state utilizzo la distribuzione degli amminoacidi

stima parametri

massima verosomiglianza

Baum-Welch's algorithm

lunghezza sequenza HMM

è stimabile

più match states, più grande la lunghezza massima possibile

più lungo il modello, più alta la lunghezza che posso generare

tutto dipende dalla probabilità di transizione da un match state al successivo

profili HMM

calcolo parametri

i parametri iniziali dipendono dal numero di simboli emessi e dal numero di transizioni

i parametri vengono quindi modificati in base all'allineamento in ragione delle conoscenze dei caratteri in una colonna e le occorenze delle transizioni

pseudocounts

si aggiungono quando una transizione o l'emissione di un particolare simbolo non si osserva

aggiungere 1 a tutte le frequenze
(regola di Laplace)

weighting

assegnare un peso alle sequenze

dipende da come lavora il software

peso minore a sequenze simili
peso maggiore a sequenze divergenti

Hmmer

tool per costruire e usare HMM di DNA e proteine

hmmbuild creare un HMM a partire da un allineamento

hmmsearch cercare un database di sequenze con un hmm

hmmalign allineare sequenze ad un hmm

SMART.EMBL

analizza sequenza e la confronta con la sua libreria di modelli di Markov che ha calcolato

Compute P(Sequence|HMM)

calcolo probabilità che la sequenza sia generata dal modello

il logaritmo negativo di esso è una misura di distanza

è lenght dependent: cosa si fa?

NORMALIZZAZIONE

z score: |s-u|/sigma

maggiore di 4 : la sequenza è molto differente da unrelated sequence