|
DATA |
TITOLO LEZIONE |
ARGOMENTI TRATTATI |
RIFERIMENTI |
|
25/2/2009 |
Introduzione al corso. Cenni di biologia molecolare 1 |
Descrizione del corso e delle modalita' di esame. Introduzione alla bioinformatica. Cenni di biologia molecolare: DNA, RNA, e proteine. La cellula. |
Materiale in copisteria sulla biologia molecolare. |
|
27/2/2009 |
Cenni di biologia molecolare 2 |
La sintesi proteica: trascrizione, traduzione, codice genetico. Le mutazioni puntuali. |
Materiale in copisteria sulla biologia molecolare. |
|
4/3/2009 |
Cenni di Biologia Molecolare 3 Pattern matching 1 |
Mutazioni cromosomiche e genomiche. Geni paralogi e ortologhi. Pattern matching esatto: Applicazioni in biologia, soluzione naive. Pattern matching esatto con preprocessing del pattern: idea. Algoritmo di Morris e Pratt. |
"Jewels of Stringology" |
|
6/3/2009 |
Pattern matching 2 |
Esempi di applicazione dell'algoritmo di Morris e Pratt. Dimostrazione della correttezza. Analisi della complessita'. |
"Jewels of Stringology" |
|
11/3/2009 |
Assegnazione argomenti per seminari. |
Descrizione del docente (a tutti gli studenti) degli argomenti proposti. Espressione delle Preferenze dei gruppi di studenti. Assegnazione argomenti quanto piu' possibile sulla base delle preferenze... |
Le assegnazioni sono riportate sul sito del corso. |
|
13/3/2009 |
Pattern matching 3 |
Limiti dell'algoritmo di Morris e Pratt. Algoritmo di Knuth, Morris e Pratt: idea, esempio, analisi della complessita'. Algoritmo di Boyer e Moore. Automa di Aho-Corasick (cenni). Algoritmo di Karp e Rabin. |
"Jewels of Stringology" |
|
18/3/2009 |
Pattern Matching 4 |
Pattern matching con preprocessing del testo: indici. Suffix tree e sua costruzione lineare. Suffix tree generalizzato. Esempi. |
"Jewels of Stringology" |
|
20/3/2009 |
Pattern Marching 5 Ricerca di motivi 1 |
Pattern matching approssimato: i vari approcci all'approssimazione e alla ricerca. Ricerca di motivi esatti con il suffix tree: analisi della complessita'. |
"Jewels of Stringology" |
|
25/3/2009 |
Ricerca di motivi 2 |
Nozioni di massimalita' di motivi. Definizioni ed esempi. Algoritmo KMR. Analisi della complessita' di KMR. Esempi. Confronto metodo col suffix tree e KMR. |
|
|
27/3/2009 |
Ricerca di motivi 3 |
Motivi strutturati: applicazioni alla localizzazione di binding site di fattori di trascrizione. Indicizzazione di motivi strutturati con il suffix tree. Motivi approssimati con Hamming Distance: ricerca con il suffix tree. |
|
|
1/4/2009 |
Ricerca di motivi 4 |
Ricerca di motivi approssimati con alfabeto degenerato. L'algoritmo KMRC. Esempi. Analisi della complessita'. |
|
|
3/4/2009 |
Allineamenti di sequenze 1 |
Il paradigma della programmazione dinamica: sottostruttura ottima di un problema. Esempi. 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 sequence comparison. |
|
17/4/2009 |
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. Allineamenti semiglobale. Esempi. Calcolo della longest common subsequence con la matrice di programmazione dinamica. Esempi. |
Materiale in copisteria su sequence comparison. |
|
22/4/2009 |
Allineamenti di sequenze 3 |
Ottimizzazioni: allineamenti in spazio lineare, allineamenti in spazio e tempo lineare per sequenze molto simili. |
Materiale in copisteria su sequence comparison |
|
24/4/2009 |
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 sequence comparison. |
|
29/4/2009 |
SEMINARIO |
SEMINARIO Maximal Repetitions in Strings di Nicola De Maio e Nino Cauli. |
|
|
6/5/2009 |
Allinamenti di sequenze 5 N.B. Si e' svolta solo un'ora di lezione a causa del BLOCCO DELLA DIDATTICA ALLE 15 per consentire la pertecipazione alle elezioni studentesche. |
Allineamento globale di due sequenze con funzione di gap penalty affine: esempio. |
Materiale in copisteria su sequence comparison. |
|
8/5/2009 |
Allineamenti di Sequenze 6 |
Allineamenti multipli: SP score, a stella, ad albero. Matrici PAM e BLOSUM. Il tool BLAST: cenni. |
Materiale in copisteria su sequence comparison. |
|
13/5/2009 |
Fragment Assembly. |
Il sequenziamnto di grandi genomi: storia. Il problema del Fragment Assembly: motivazioni e rilevanza. Soluzione greedy. Problemi: copertura, contaminazioni, chimere, orientamento ignoto, ripetizioni lunghe e corte. Possibili soluzioni: approcci euristici. |
Materiale in copisteria su Fragment Assembly |
|
15/5/2009 11-13 e 14-16 |
Genome Rearrangement 1. |
Breakpoint: modello dei punti di rottura casuali VS modello dei punti di rottura fragili. Genomi mediani. Cluster mediano di geni. |
|
|
20/5/2009 |
Genome rearrangement 2 |
Assegnamento di geni ortologhi. Sorting di genomi per inversioni orientate in tempo O(n log n). |
|
|
22/5/2009 11-13 e 14-16 |
Ricerca di similarita' |
Ricerca di repeat in genomi incompleti. Allineamento multiplo basato su segmenti. Allineamnto di LCS di suffissi consecutivi. Ricerca di proteine simili tramite vincoli sull'mRNA. |
|