Algoritmi e linguaggi per bioinformatica - ALGORITMI PER BIOINFORMATICA (2013/2014)

Obiettivi formativi

1. comprensione di alcuni dei principali problemi e algoritmi alla base della bioinformatica (allineamento, filogenetica); 2. comprensione delle principali problematiche legate alla computazione (complessita', efficienza, fattibilita').

ANALISI DI ALGORITMI

Introduzione all'analisi di algoritmi, analisi di tempo e spazzio; notazione per l'analisi di complessita' (O-notation), crescita di funzioni; formalismo su stringhe; combinatorica su stringhe;

ALLINEAMENTO DI SEQUENZE

applicazioni; allineamento di coppie di sequenze; ricerca esaustiva; programmazione dinamica (DP): algoritmo di Needleman-Wunsch (allineamento globale); algoritmo di Smith-Waterman (allineamento locale); altre varianti di questi algoritmi (cenni); allineamento multiplo; matrici scoring: PAM (generazione, applicazioni); euristiche per l'allineamento di sequenze: dotplots, BLAST;

STATISTICA

Richiami di statistica di base (statistica descrittiva, test d'ipotesi, P value, errori di I e II tipo);

FILOGENETICA

introduzione a grafi ed alberi; numero di alberi filogenetici; dati basati su distanza: UPGMA; dati basati su caratteri: Perfect Phylogeny (PP); Small Parsimony: algoritmo di Fitch; Large Parsimony: euristiche (cenni)

esame scritto e presentazione di un progetto.