Bioinformatica: parte 2

HIDDEN-MARKOV MODELS

Fino ad ora abbiamo detto che, la probabilità di avere un certo residuo in una specifica posizione di una sequenza dipende solo

dalla frequenza di quel carattere nella sequenza stessa, tuttavia, nelle sequenze biologiche con significato funzionale, questa

assunzione non è quasi mai verificata.

Ad esempio, il dinucleotide GT caratterizza le giunzioni esone/introne; in questo caso, la probabilità che una T indichi l’inizio di

un introne dipende dal suo essere preceduta da una G (probabilità condizionate).

I processi statistici che descrivono il caso in cui un evento dipende da ciò che lo precede si chiamano “processi di Markov” e le

successioni di tali eventi prendono il nome di catene di Markov.

Una sequenza “S” di numeri, nucleotidi o di residui (S = [s1,s2,s3,...,sn]) può essere considerata una catena di Markov di ordine

“k” se è vero che la probabilità di avere l’elemento “x” nell'i-esima posizione di S dipende solo dai k elementi immediatamente

precedenti; praticamente, nelle catene di Markov, possiamo avere l’ordine di una catena, chiamato K, il quale ci dice quanti

sono gli elementi presenti prima che devo considerare per avere la probabilità di avere quel residuo in quella particolare

posizione che stiamo considerando:

- se k=0, la statistica viene determinata semplicemente dalle frequenze degli elementi stessi, ovvero, ogni singola posizione

dipende solo dalla singola posizione, quindi non bisogna considerare nessun residuo che lo precede.

- se k=1, per avere la probabilità del residuo in posizione 4, devo considerare solamente il residuo in posizione 3; se K=1 e ad

esempio volessi trovare la probabilità di avere T in una determinata posizione, questa sarà influenzata da quello che c’è subito

prima della T

Le catene di markov si possono rappresentare attraverso i cosiddetti grafi orientati, costituiti da un insieme di nodi e di archi:

Giunti a questo punto, introduciamo il concetto di:

- Grafo semplice: è costituito da punti, detti vertici o nodi, e da linee che li uniscono, dette lati o spigoli o archi (es. i nodi sono

proteine, gli archi sono interazioni tra le proteine).

- Grafo orientato: è un grafo caratterizzato da un verso; in un grafo orientato ogni nodo corrisponde ad uno “stato” (es.

amminoacido).

In particolare, lo stato iniziale e lo stato finale sono due particolari nodi e gli archi sono caratterizzati da un verso.

- Un grafo pesato: l’arco può avere anche un peso; la dimensione dell’arco dipende dal peso che ha, più è pesante più è grande.

- Un grafo bipartito: grafo indiretto in cui i vertici possono essere posizionati in due insiemi; in altre parole, i nostri vertici

possono essere divisi in due classi (es. i vertici della classe geni e i vertici della classe malattia) e quello che succede è che, da

ogni vertice di una classe (es. classe geni), potranno partire degli archi che andranno verso l’altra classe (classe malattia) e così

facendo potremo vedere i vari collegamenti (ad es. il gene 1 è collegato a tutte le malattie del gruppo 2).

Qualsiasi vertice dell’insieme 1 può essere connesso a qualsiasi altro vertice dell'insieme 2, ma non sono permessi archi tra i

vertici di un medesimo insieme.

- Un grafo multi-arco: è un grafo contenente archi multipli oppure paralleli che sono incidenti sugli stessi due vertici; in

sostanza quindi, quando abbiamo più archi che collegano due vertici si parla di grafi multipli (es. in questo caso abbiamo tre

archi che collegano 1 e 3).

Un esempio l’abbiamo visto su STRING, in quanto, tra due nodi del nostro interattoma, potevamo avere degli archi multipli, i

quali rappresentavano ognuno un metodo con il quale era stata certificata quella interazione.

- Un ipergrafo: consiste in un insieme di vertici e un insieme di iperarchi, ovvero degli archi che possono collegare più di due

vertici (es. in questo caso, l’iperarco che collega 1, 2, 3 è un solo arco che allo stesso tempo sta collegando 3 vertici).

Proprietà topologiche dei grafi:

- Il grado di un nodo è il numero di archi che partono da un nodo:

In questo caso ad esempio, per il nodo 6 il grado è 1, per il nodo 4 è 3, per il nodo 3 è 2 e così via.

Con questa tecnica io riesco a dare importanza ai nodi presenti all’interno del grafo, in quanto riesco a dire qual è il nodo hub,

ovvero, quello collegato al maggior numero di altri nodi.

Il grado generale di tutto il network è dato dalla somma dei gradi di tutti i suoi nodi (quanti partono e arrivano al nodo).

- La distanza è definita come la lunghezza del percorso più corto (shortest path), ovvero, il numero minimo di archi che devono

essere attraversati per raggiungere il nodo: ci possono essere diversi percorsi.

Se due shortest paths di lunghezza identica coesistono, qualsiasi di essi può essere usato.

Ad esempio, se io volessi calcolare la distanza tra il nodo 1 e il nodo 6, quello che devo fare è vedere il numero di archi che

intercorrono tra essi due; ad esempio:

. Un percorso possibile per arrivare da 1 a 6 potrebbe essere: 1 – 2 – 3 – 4 – 6

. Un altro percorso possibile potrebbe essere 1 – 5 – 5 – 6; ovviamente questo è il percoso più corto, di conseguenza, questa è

la distanza.

- Coefficiente di clustering: è la misura che mostra se un network o un nodo ha la tendenza a formare comunità (o cluster)

altamente connesse tra di loro; il coefficiente di clustering di un nodo è definito come il numero di archi tra i suoi vicini diviso

per il numero delle possibili connessioni tra tali vicini.

È una misura compresa tra 0 e 1: tanto più è vicino ad 1, tanto più si ha un’alta tendenza a formare clusters.

Vediamo un esempio:

In questa rappresentazione, i nodi rappresentano le pagine di Wikipedia mentre gli archi sono i link che ci consentono di andare

da una pagina all’altra.

Vedendo bene si formano 3 comunità e all’interno di ognuna ci sono tante comunità più piccole; per fare un esempio, posso

andare nella sezione “sport” (che in questo caso rappresenta una comunità) e poi all’interno di ogni sezione ci sono i vari

collegamenti con i calciatori, pallavolisti, nuotatori ecc. (i quali invece rappresentano i vari nodi), poi vado all’interno della

sezione “ristorazione” (che in questo caso rappresenta un’altra comunità) e all’interno di essa trovo vari collegamenti con

cucina, bar, fast-food ecc. (che in questo caso rappresentano i vari nodi).

In particolare, ciascun nodo presente all’interno della comunità, si può collegare ad un altro nodo presente all’interno della

stessa comunità (ad es. un calciatore che gioca insieme ad un alto calciatore) ma anche con nodi presenti all’interno di un’altra

comunità (ad es. un calciatore potrebbe interessarsi anche di cucina), tuttavia, questi collegamenti tra nodi diversi sono minori;

in sostanza quindi, i nodi che fanno parte del gruppo “sport” sono più connessi tra di loro rispetto alle connessioni che hanno i

nodi del gruppo “sport” con i nodi del gruppo “ristorazione”.

- Misura di centralità: è una misura che mostra se un nodo ha la tendenza a formare comunità (o cluster) altamente connesse;

in pratica, le misure di centralità sono misure che possono essere riferite a nodi o archi e rappresentano la loro importanza per

la connettività o il flusso di informazione nel network (es. esempio, se tolgo un nodo, tutto il cluster si disgrega).

Come si costruisce l’hidden-markov model

Un hidden-markov model è un grafo orientato, quindi abbiamo dei nodi e degli archi e quest’ultimi hanno una direzione; ogni

nodo rappresenta uno “stato” all’interno del nostro grafo.

Ad esempio, in questo caso ci sono 2 nodi, uno “stato iniziale” e uno “stato finale”:

In questo caso invece, ci sono 6 stati, uno iniziale, uno finale e 4 stati intermedi; questi stati sono connessi tra loro da archi, i

quali sono sempre caratterizzati da un verso (si va sempre dallo stato iniziale a quello finale):

Questa catena di Markov può generare diverse sequenze di stati:

- 1234;

- 234;

- 14;

- 12121214;

- 21234

E altre ancora…

Esempio di grafo orientato: gli archi orientati rappresentano le transizioni tra uno stato e l’altro ed ogni transizione può essere

caratterizzata da una

precisa probabilità:

In sostanza quindi, così facendo, ovvero calcolando le varie probabilità delle varie transizioni di ciascun percorso (sequenza), ad

ogni sequenza di stati si può associare la sua probabilità di essere generata; ad esempio:

- La probabilità di generare la sequenza (1234) = (probabilità di arrivare a 1) x (probabilità di arrivare a 2) x (probabilità di

arrivare a 3) x (probabilità di arrivare a 4) = 0.5 x 0.1 x 0.75 x 0.8= 0.03 (probabilità di avere la sequenza 1234).

- La probabilità di generare la sequenza (2334) = (probabilità di arrivare a 2) x (probabilità di arrivare a 3) x (probabilità di

ritornare a 3) x (probabilità di arrivare a 4) = 0.5 x 0.75 x 0.2 x 0.8= 0.06 (probabilità di avere la sequenza 2334).

- La probabilità di generare la sequenza (123) = (probabilità di arrivare a 1) x (probabilità di arrivare a 2) x (probabilità di

ritornare a 3) = la sequenza non finisce quindi è un errore; questo perché dal nodo numero 3 non posso arrivare alla fine, in

quanto dovrei passare per forza dal nodo numero 4.

Consideriamo due diverse sequenze nucleotidiche:

1) Una in cui tutti i dinucleotidi sono equiprobabili

2) L’altra in cui le frequenze dei nucleotidi dipendono dal residuo precedente (catena di Markov di ordine k= 1)

In questo grafo abbiamo 4 possibili stati e possiamo indicare accanto ad ogni arco la probabilità di transizione tra uno stato e

l’altro nella costruzione della sequenza; ad esempio, noi possiamo dire che è più facile che dopo una A ci sia una C (quindi

sull’arco A-C mettiamo una probabilità più alta) è più difficile che dopo una A ci sia una G (quindi sull’arco A-G mettiamo una

probabilità più bassa).

In questo caso consideriamo due diverse sequenze nucleotidiche:

1) Una in cui tutti i dinucleotidi sono equiprobabili, quindi la probabilità di transizione è uguale su tutti e quattro.

2) In questo caso i dinucleotidi non sono equiparabili, quindi la probabilità di transizione sarà diversa su tutti e quattro.

Ovviamente, in questo caso, le sequenze che usciranno dal primo grafo saranno diverse dalle sequenze che usciranno dal

secondo grafo; q