Le catene di Markov sono semplici successioni di numeri o di caratteri in cui l’identità di un elemento dipende solo dall’identità degli elementi precedenti.
Le catene di Markov possono essere utilizzate per calcolare il numero atteso di occorrenze di una certa stringa oligonucleotidica.
Schema superiore : Rappresentazione grafica di una catena di Markov, in cui ogni elemento dipende dall’elemento precedente. Possibili sequenze di stati generate da questa catena di Markov: 1234; 234; 14; 12121214; 21234.
Schema inferiore: Catena di Markov con probabilità di transizione. La probabilità che una determinata successione di stati venga generata è data dal prodotto delle varrie probabilità di transizione che si succedono nel corso dell'emissione.
Le catene di Markov nascoste (Hidden Markov Models o HMM) sono composte da un certo numero di stati che possono, per esempio, corrispondere a residui di una sequenza, a colonne di un allineamento multiplo oppure a posizioni in una struttura proteica tridimensionale. I vari stati sono interconnessi tramite precise probabilità di transizione. La sequenza di stati è una catena di Markov, in quanto la scelta dell'elemento successivo dipende dallo stato attuale. Gli stati sono peṛ nascosti da cui il nome Hidden Markov Models.
Gli HMM sono strettamente correlati alle reti neurali, in quanto ne rappresentano una particolare realizzazione. Un semplice esempio di HMM è riportato nella figura sottostante. I due riquadri in colore rappresentano stati dell'HMM in grado di emmettere nucleotidi, con le loro probabilità.
I riquadri a sinistra e a destra rappresentano gli stati iniziale (I) e finale (F) e le probabilità di transizione da uno stato all'altro sono riportate accanto alle frecce che li uniscono. Questo semplice esempio presenta solo due stati nascosti completamente interconnessi e non l'HMM che più frequentemente viene usato nelle applicazioni biologiche.
Catena di Markov che genera sequenze di acidi nucleici