|
DATA |
TITOLO LEZIONE |
ARGOMENTI TRATTATI |
RIFERIMENTI |
|
1/10/2007 |
Introduzione del corso. Cenni di Complessita' Computazionale 1 |
Descrizione del corso e delle modalita' di esame. Complessita' di un algoritmo. Complessita' di un problema. |
Lucidi del docente disponibili in copisteria. |
|
2/10/2007 |
Cenni di complessita' computazionale 2 |
Esercizio sulla complessita'. Le classi P e NP. Problemi intrattabili. |
Lucidi del docente disponibili in copisteria. |
|
8/10/2007 |
Cenni di complessita' computazionale 3 |
Riduzioni polinomiali (cenno) e problemi NP-completi. Approcci per problemi non trattabili: Approssimazioni ed euristiche. |
|
|
9/10/2007 |
Approcci a problemi non trattabili. I principali costrutti dei linguaggi di programmazione. |
Approssimazioni: la clase APX. Euristiche: branch and bound, algoritmi probabilistici. I costrutti dei linguaggi di programmazione: esempi di utilizzo. |
Materiale in copisteria. |
|
15/10/2007 |
Pattern Matching 1 |
Pattern Matching esatto: algoritmo naive e analisi della complessita'. Metodi con preprocessing del pattern. |
Materiale in copisteria su Pattern Matching. |
|
16/10/2007 |
Pattern Matching 2 |
Algoritmo KMP. Dimostrazione di correttezza. Esempi di applicazione. Analisi della complessita'. |
Materiale in copisteria su Pattern Matching. |
|
22/10/2007 |
Pattern Matching 3 |
Metodi basati su preprocessing del testo: indicizzazioni. Il suffix tree. Esempi. |
Materiale in copisteria su Pattern Matching. |
|
23/10/2007 |
Pattern Matching 4 |
Il suffix tree generalizzato. Pattern Matching approssimato: distanze di Hamming e di edit, alfabeti degenerati, simbolo wild card. Pattern Matching approssimato con il suffix tree. |
Materiale in copisteria si Pattern Matching. |
|
29/10/2007 ore 16 |
Allineamenti di sequenze 1 |
Allineamento globale di due sequenze. Il problma e dimensione dello spazio di ricerca. Calcolo dello score e dell'allineamento ottimo in tempo e spazio quadratico con la matrice di programmazione dinamica. Esempi. |
Materiale in copisteria su allineamenti. |
|
30/10/2007 ore 16 |
Allineamenti di sequenze 2 |
Allineamento locale: definizione e soluzione con la matrice di programmazione dinamica. Esempi. Allineamento semiglobale: definizione e soluzione con la matrice di programmazione dinamica. Esempi. |
Materiale in copisteria su allineamenti. |
|
12/11/2007 ore 16 |
Allineamenti di sequenze 3 |
Ottimizzazioni: allineamenti in spazio lineare, allineamenti in spazio e tempo lineare per sequenze molto simili. Calcolo della longest common subsequence con la matrice di programmazione dinamica. Esempi. |
Materiale in copisteria su allineamenti. |
|
13/11/2007 ore 16 |
Allineamenti di sequenze 4 |
Calcolo dell'allineamento ottimo con funzioni generali per le gap penalties. Calcolo dell'allineamento ottimo con funzione di gap penalty affine. Esempi. |
Materiale in copisteria su allineamenti. |
|
19/11/2007 ore 16 |
Allineamenti multipli di sequenze 1 Ricorstruzione di alberi filogenetici 1 |
Allineamenti multipli: SP score, a stella, ad albero. Matrici PAM. Il tool BLAST. Alberi filogenetici: introduzione. |
Materiale in copisteria su sequence comparison. Materiale in copisteria su alberi filogenetici. |
|
20/11/2007 ore 16 |
Ricostruzione di alberi filogenetici 2 |
Alberi filogenetici radicati e non: enumerazione. Metodi basati su distanze: algoritmo UPGMA. Esempi. |
Materiale in copisteria su alberi filogenetici. |
|
26/11/2007 ore 16 |
Pattern Matching approssimato |
Algoritmo Boyer Moore in versione approssimata per sequenze geniche |
|
|
27/11/2007 |
Ricostruzione di alberi filogenetici 3 |
Algoritmo Neighbor Joining. Esempi. Metodi basati su caratteri: Algoritmo di Fitch. Esempi. |
Materiale in copisteria su alberi filogenetici. |
|
3/12/2007 |
Ricerca di motivi 1 |
Ricerca di motivi esatti col il suffix tree. Esempi. Algoritmo KMR. Esempi. Motivi strutturati e applicazione alla ricerca di binding site di fattori di trascrizione. |
|
|
4/12/2007 |
Allineamenti multipli di sequenze 2 |
Filtri per allineamenti multipli locali approssimati con Hamming Distance. Estensione al caso della Edit Distance. |
|
|
10/12/2007 |
Esercitazione |
Esercizi sul suffix tree. Esercizi di scrittura in pseudocodice di semplici algoritmi su vettori. Valutazione delle complessità. |
|
|
10/12/2007 ore 16 |
Fragment Assembly |
Importanza del problema nel sequenziameno di genomi. Possibili approcci e complicazioni. Suo legame con il problema "Shortest common superstring". |
|
|
11/12/2007 |
Esercitazione |
Esercizi di scrittura di pseudocodice e di valutazione della complessità. Esercizi su allineamenti. |
|