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