Docente: Nadia Pisanti

[9 Gennaio 2012] La lezione di Venerdi' 13 alle ore 11 si terra' in aula PS2.

[4 Gennaio 2012] Su richiesta del rappresentante degli studenti, la lezione di Lunedi' 9/1/2012 e' posticipata a Venerdi' 13 alle 11 in un'aula che verra' comunicata al piu' presto.

[14 Ottobre 2011] Si informa/ricorda che il giorno 31 Ottobre il calendario accademico prevede sospensione della didattica.

[3 Ottobre 2011] Abbiamo stabilito che in linea di massima l'orario di ogni lezione sara' il seguente: 9,15-10.45 (senza pausa), per permettere agli studenti pendolari di arrivare in tempo e a tutti di raggiungere un'altra lezione alle 11 presso un altro polo didattico.

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

• REGISTRO DELLE LEZIONI