Docente: Nadia Pisanti
[13 Maggio 2014] Sono pubblica le date degli appelli: 26/6 ore 11 aula I1, e 16/7 opre 11 aula I1.
[8 Aprile 2014] La lezione di Martedi 15 non avra' luogo.
[11 Marzo 2014] Per recuperare la lezione di oggi (molti assenti) e quella della prossima settimana (che non si terra'), abbiamo concordato di fare due ore piene 9-11 con solo una breve pausa nei giorni 25 Marzo e 1 Aprile. Pertanto, in tali giorni le lezioni inizieranno alle 9:00.
[10 Marzo 2014] La lezione del 18 Marzo NON avra' luogo.
[Febbraio 2014] Dal giorno 4 Marzo le lezioni si terranno in aula D3.
[Maggio 2013] Creata la pagina del Corso per l'anno accademico 2013-2014.
L'obiettivo del corso è di fornire allo studente una panoramica di algoritmi concepiti per lo studio di sequenze genomiche. Verra' prestata attenzione sia agli aspetti teorici e combinatori che a quelli pratici posti dai vari problemi quali il sequenziamento di interi genomi, l'allineamento di sequenze, la ricerca di pattern ripetuti e di lunghe ripetizioni approssimate, il calcolo di distanze genomiche, e altri problemi biologicamente rilevanti per lo studio di sequenze molecolari.
LA COMPLESSITA' COMPUTAZIONALE Complessita' in tempo e spazio di un algoritmo. Complessita' e trattabilita' di un problema.
ALLINEAMENTI DI SEQUENZE Problema dell'allineamento di sequenze: algoritmo di programmazione dinamica per l'allineamento globale, locale, e semi-globale di coppie di sequenze, e sue possibili ottimizzazioni. Allineamento con 'affine gap penalty function'. Allineamenti multipli.
RICERCA DI PATTERN IN UN DATA BASE Problema della ricerca di un pattern in un data base: possibili soluzioni e analisi comparativa delle loro performance e complessita'. Metodi che fanno preprocessing del pattern: Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin. Metodi di indicizzazione del data base.
FRAGMENT ASSEMBLY Ricostruzione di sequenze biologiche 'in silico' dopo il sequenziamento: algoritmi e strutture dati per il metodo Sanger e loro limiti. Che cosa cambia con le tecniche di sequenziamento del “New Generation Sequencing”.
PER LA PARTE DI COMPLESSITA': parte dei capitoli 1 e 2 del libro “An Introduction to Bioinformatics Algorithms” di Neil C.Jones e Pavel A.Pevzner, MIT Press, 2004.
PER LA PARTE DI ALLINEAMENTI DI SEQUENZE: parte del capitolo di libro allineamenti.pdf
PER LA PARTE DI FRAGMENT ASSEMBLY: parte del capitolo di libro fragmentassembly.pdf
PER LA PARTE DI PATTERN MATCHING: patternmatching1.pdf e patternmatching2.pdf