Progetto d'esame per il corso di Metodi Bioinformatici 2011-12

Predizione della funzione dei geni con metodi basati su random walk 

Il progetto ha l'obiettivo di applicare metodi di random walk all'analisi di reti di interazione funzionale per predire le funzioni dei geni in un organismo modello (lievito).

Il progetto si articola in 2 parti (piu' una terza opzionale).

1. Implementazione in R dell'algoritmo Random Walk.
2. Ranking dei geni del lievito rispetto a 168 classi funzionali di FunCat 
3. (opzionale) Analisi dei geni "top ranked" non annotati per alcune classi FunCat.

1. Implementazione in R dell'algoritmo Random Walk.

Si implementi la funzione RW.
Tale funzione riceve in ingresso una matrice di adiacenza pesata di un grafo, l'insieme dei nodi positivi e ritorna lo score (probabilita') predetta dall'algoritmo per tutti i nodi del grafo.

Argomenti di ingresso:
- W : matrice di adiacenza (pesata) del grafo
- ind.positives: indici del "core" dei vertici positivi del grafo. Gli indici si riferiscono alle righe della matrice W.
- tmax : numero massimo di iterazioni consentite
Opzionalmente si puo' aggiungere un argomento eps per le condizioni di convergenza

Uscita:
- un vettore p delle probabilità predette per ciascun vertice

Si possono anche aggiungere altri parametri purche' debitamente documentati e giustificati.

 2. Ranking dei geni del lievito rispetto a 168 classi funzionali di FunCat.

Si applichi la funzione RW al ranking dei geni del lievito rispetto alle classi funzionali della tassonomia FunCat: 
http://www.helmholtz-muenchen.de/en/mips/projects/funcat/index.html .

a. Dati
Dalla directory http://homes.dsi.unimi.it/~valenti/MB201112/esame/ sono scaricabili i seguenti file:

- Yeast.interaction.data.rda. Tale file binario R compresso contiene la matrice
Yeast.interaction.data, che rappresenta una matrice di interazione funzionale fra 1901 geni del lievito, ottenuta tramite l'integrazione di 6 diverse sorgenti di dati. Per una descrizione dei data set integrati si veda, ad es: l'articolo: 
 M. Re, G. Valentini, Simple ensemble methods are competitive with state-of-the-art data integration methods for gene function prediction  Journal of Machine Learning Research, W&C Proceedings, vol.8: Machine Learning in Systems Biology, pp. 98-111, 2010.
Yeast.interaction.data è una matrice 1901X1901 i cui valori Yeast.interaction.data[i,j] rappresentano relazioni/similarita' funzionali fra i geni i e j. E' una named matrix simmetrica in cui i nomi delle colonne e delle righe sono gli Ordered Locus Name (OLN) dei geni del lievito. 

- Yeast.FunCat.rda. Contiene due oggetti R:
I) Yeast.FunCat.ann: matrice delle annotazione FunCat del lievito: e'una named matrix le cui righe corrispondono a 1901 geni del lievito (nello stesso ordine di Yeast.interaction.data) e le cui colonne corrispondono a 168 classi funzionali FunCat. Se   Yeast.FunCat.ann[i,j]==1 allora il gene i appartiene alla classe funzionale j, altrimenti  Yeast.FunCat.ann[i,j]==0.
II) FunCat.classes:un data frame la cui prima colonna riporta gli identificatori FunCat (corrispondenti ai nomi delle colonne di  Yeast.FunCat.ann), e la seconda colonna una breve descrizione della classe funzionale.

b. Ranking dei geni e valutazione delle prestazioni.
Si suddividano i geni in test set e train set: i primi 600 geni di Yeast.interaction.data rappresentano il test set, i rimanenti 1301 il training set.
Applicare RW ad ognuna delle classi funzionali e calcolare l'AUC (Area Under the ROC Curve) sul test set per ogni classe. N.B.: RW puo' utilizzare solo i geni annotati del training set per assegnare le probabilita' ai geni del test set e l'AUC va calcolata solo sui geni del test set.
L' AUC sul test va calcolata:
- per ogni classe
- come valor medio fra tutte le classi.
Per calcolare i valori dell'AUC si usi la funzione AUC.single.over.classes del package PerfMeas (scaricabile da CRAN: http://cran.r-project.org/).

Si ripeta l'esperimento con Random walk ad 1, 2, 3 e 10 step e si confrontino i risultati. 

3. Analisi dei geni "top ranked" non annotati (Opzionale). Si selezionino le 3 classi per cui si e' ottenuta l'AUC piu' elevata. Per tali 3 classi si usino come "positivi" tutti i geni annotati per quella classe (senza distinguere fra train e test set). Si selezionino poi per ogni classe i primi 5 geni top ranked (cioe' quelli che hanno ottenuto la probabilita' piu' alta) NON annotati per quella classe. Si controlli tramite ricerca sul sul sito http://mips.helmholtz-muenchen.de/genre/proj/yeast/ o sul sito SGD e su PubMed se esita una qualche evidenza di associazione funzionale del gene con la classe funzionale considerata.

4. Scrivere un report sintetico che illustri l'algoritmo Random Walk implementato al punto 1  ed i risultati ottenuti al punto 2 (e, opzionalmente, al punto 3).
Riportare il codice R per la funzione RW e lo script degli esperimenti per il punto 2 b). Il codice va commentato: il codice di ogni funzione deve essere preceduto da commenti che spieghino sinteticamente a cosa serve la funzione stessa, il tipo ed il significato di ogni argomento di ingresso, il tipo ed il significato dell'output della funzione.